전자 문서 보안

타이렐(Tyrell) 사는 문서의 생성, 열람, 편집, 배포를 모두 제어하는 최첨단 전자 문서 시스템을 사용한다. 문서 보안은 접근 제어 목록(ACL, Access Control List)으로 관리된다. ACL은 문서에 접근할 수 있는 개체(entity)들의 집합을 정의하고, 각 개체마다 그 개체가 가진 권한(right)들의 집합을 정의한다.

• 개체는 대문자 알파벳으로 나타낸다. 하나의 개체는 한 개인일 수도 있고 부서 전체일 수도 있다.
• 권한은 소문자 알파벳으로 나타낸다. 예를 들어 a는 추가(append), d는 삭제(delete), e는 편집(edit), r은 읽기(read)를 뜻한다.

문서의 ACL은 문서와 함께 저장되지만, 별도의 로그 서버에 저장되는 ACL 로그도 존재한다. 모든 문서는 아무에게도 어떤 권한도 주지 않는 빈 ACL로 시작한다. 문서의 ACL이 변경될 때마다 로그에 새 항목이 하나 기록된다.

각 항목은 ExR 형태이다. 여기서 E는 비어 있지 않은 개체 집합, R은 비어 있지 않은 권한 집합이며, x는 +, -, = 중 하나이다.

• E+R: E의 모든 개체에게 R의 모든 권한을 부여한다.
• E-R: E의 모든 개체에서 R의 모든 권한을 제거한다.
• E=R: E의 모든 개체가 정확히 R의 권한만 갖도록(그 외의 권한은 없도록) 설정한다.

이미 가진 권한을 다시 부여하거나 갖고 있지 않은 권한을 제거하는 등, 항목이 중복(redundant)일 수도 있다. 로그는 이러한 항목들을 쉼표로 구분해 오래된 것부터 최신 순으로 나열한 목록이다. 항목은 누적 적용되며, 충돌이 생기면 더 최신 항목이 우선한다.

타이렐 사는 주기적으로 보안 점검을 실시하는데, 로그로부터 각 문서의 현재 ACL을 계산한 뒤 문서와 함께 저장된 실제 ACL과 비교한다. 둘이 다르면 보안 침해를 뜻한다. 주어진 ACL 로그로부터 현재 ACL을 계산하는 프로그램을 작성하라.

입력은 하나 이상의 ACL 로그로 이루어진다. 각 로그는 길이가 3자 이상 79자 이하이며 한 줄에 하나씩 주어진다. 마지막에는 입력의 끝을 알리는 #만 있는 줄이 온다. 각 로그는 위에서 정의한 형식을 따르며 공백을 포함하지 않는다.

각 로그마다 한 줄을 출력한다. 먼저 로그 번호(로그는 1부터 순서대로 번호를 매긴다)를 쓰고, 이어서 콜론 :을 쓴 다음, 아래 형식에 맞춰 현재 ACL을 출력한다. 규칙은 다음과 같다.

1. 출력에는 공백이 없다.
2. 개체는 알파벳 순으로 나열한다.
3. 한 개체의 권한들도 알파벳 순으로 나열한다.
4. 현재 아무 권한도 없는 개체는 (로그 항목에 등장했더라도) 나열하지 않는다. 따라서 ACL이 완전히 비어 있을 수도 있다.
5. 알파벳 순으로 연속한 둘 이상의 개체가 정확히 같은 권한을 가지면, 그 권한들은 해당 개체들을 모두 나열한 뒤 한 번만 출력한다.