반응형

 저는 모 대회에서 3개 이상 푼 분을 절반 이상으로 예측했습니다. 심지어, 평균을 3.x개라고 예측하기도 했습니다만, 실제 결과는 상이하였습니다. 3번 문제였던 이 문제는 난이도가 그렇게 어려운 편이 아니였습니다. 그래서 문제 분석을 풀이보다 중점적으로 하고자 합니다.

 


 먼저, 문제에서 구하고자 하는 것은 무엇인가요? 연산이 성공하면 1을, 아니면 0을 출력하라는 것입니다. 연산이 무엇인가요? R, W, X 중 하나임을 볼 수 있습니다. USER_NAME, FILE_NAME, operation 순서로 주어집니다. 그리고, 이것은 유저 USER_NAME이 파일 FILE_NAME인 파일에 대해 operation을 수행할 수 있는지를 의미함을 알 수 있습니다.

 

 다시 문제를 이해해 봅시다. 구하고자 하는 것이 무엇인가요? 어떤 파일에 대해서 특정 유저가 읽기, 쓰기, 실행을 할 수 있는가? 그러면 권한에 대한 메타 정보가 어디에 주어지를 봐야 합니다.

 

 File에 대한 정보가 주어질 때 같이 주어집니다. FILE_NAME이 FILE_PERMISSION을 가지는데, 해당 파일의 소유자가 OWNER이고, 소유 그룹은 OWNED_GROUP이다. 여기서 문제에서 주어지는 쿼리랑, 같은 속성을 가지는 것 끼리 비슷한 색상으로 묶었음을 알 수 있는데요. 문제 파악을 용이하게 하기 위함입니다. 파일에는 권한이 있고, 소유자와 소유 그룹이 있답니다. 그러면 퍼미션은 뭘 의미할까요?

 

 문제의 맨 위에 권한이란, 3자리의 숫자로 이루어져 있다고 되어 있습니다. 이들이 무엇인가요?

 

 [표 1] 밑에 설명하는 부분을 보면 요래 정리할 수 있습니다. 문제는 소유자의 권한, 그룹의 권한, 그 외의 권한을 누가 가져가느냐입니다. 이는 [표 2]를 통해 아래와 같이 정리할 수 있습니다.

 

 여기까지 정리해 봅시다. 결국 우리는 첫 번째로 어떤 것을 알면 되나요? 해당 유저가 파일의 소유자인지, 소유 그룹에 속하는지, 아무것도 아닌지를 알면 됩니다. 그러면 유저가 어느 그룹에 속하는지를 알아야 겠군요. 이건 입력 설명에 주어지네요.

 

 

  사실 여기까지 정리했다면 어렵지 않게 문제를 푸실 수 있습니다. 이 내용을 바탕으로 유저가 해당 파일의 소유자인지, 소유 그룹에 속하는지, 둘 다 아닌지 빠르게 판단해 봅시다.

 


 우리가 해결해야 하는 것은 유저가 해당 파일의 소유자인지, 소유 그룹에 속하는지 빠르게 판단하는 것입니다. 유저가 속한 그룹은 많아야 10개이고, 유저 그룹의 문자열 길이는 10 이하입니다. 따라서, 그냥 아래와 같이 자료구조를 설계하셔도 됩니다.

 

 

 user_groups[x]는 유저 x가 속한 그룹들을 저장합니다. User가 속한 그룹을 선형 탐색해도 사실 문제는 없습니다만, 어떤 키가 있는지 빠르게 판단하기 위해서 hash를 쓰기도 합니다. 유저는 최대 50만명 있기 때문에, 유저를 빠르게 찾기 위해서는 hash 기반의 구조를 써야 하는 것은 명백합니다. 저 구조에서는 키 하나에 multiple value가 있습니다. 따라서, 이러한 것을 관리하기 위해서, value를 리스트나 hash를 쓸 수 있습니다. 즉, hash의 hash를 쓰는 것입니다. 매우 많이 쓰는 패턴이므로 알아두시는 게 좋습니다.

 

 user_groups[x][y]는 유저 x가 그룹 y에 속한다는 의미입니다. 혹은 아래와 같이 설계할 수도 있습니다.

 

 

 group_user[x][y]는 그룹 x에 유저 y가 있다는 의미입니다. 그룹 하나에 유저는 최대 50만명까지 있을 수 있고, 그룹도 최대 10만개까지 있기 때문에, 이 경우에는 hash의 hash가 강제됩니다. 제 깃허브의 파이썬 코드는 후자의 방법을 사용하였습니다. 그런데, 이 로직을 어디에 쓸까요?

 

 

 당연하게도 파일 권한의 몇 번째 숫자를 가져올 건지 알아내기 위해 씁니다. user가 파일의 소유자인지 판단하는 것은 쉽습니다. 소유자가 아닌 경우, 소유 그룹인지를 판단해야 합니다. 이를 수행하기 위해, 그룹이 어떤 유저들을 들고 있는지, 혹은 유저가 어떤 그룹에 속해 있는지에 대한 자료구조가 필요합니다. 유저는 여러 그룹에 속할 수 있고, 그룹 또한 여러 유저를 가질 수 있기 때문에, 해쉬의 해쉬가 적합한 구조입니다. key multi value 문제에서 보통 hash of hash를 쓰곤 하는데, 이 문제에서도 정확히 그걸 물어본 셈입니다. 이제 코드를 보겠습니다.

 

 

  add_group은 user가 group에 속한다는 정보를 추가합니다. 파이썬에서는 딕셔너리가 hash 기반의 구조이기 때문에, 딕셔너리의 딕셔너리 구조를 취했습니다. 이렇게 정보를 넣으면, 해당 유저가 특정 그룹에 속하는지 판단하기 위해, user in grp[group] 문장 한 번에 할 수 있습니다.

 

 

 그룹에 대한 정보가 들어올 때에는 어떻게 하면 될까요? 유저 u는 그룹 u에 속합니다. 19번째 줄은 유저 u가 그룹 u에 속한다는 정보를 넣어줍니다. 다음에, 유저가 속한 그룹 정보가 들어온 경우, 그룹에 유저가 속했다는 정보를 넣어줍니다. 이제, 우리는 쿼리가 들어올 때 마다, 파일 퍼미션의 몇 번째 숫자를 가져와야 하는지에 대해 알게 되었습니다.

 

 


 이제 각 숫자가 어떤 퍼미션을 가지는지 구하는 것이 문제입니다. 이에 대한 판단은 익히 알려진 비트 연산자를 활용할 수 있습니다. 그런데, 다른 방법이 없을까요? 사실 권한의 종류가 8개이기 때문에, 하드 코딩해도 됨을 알 수 있습니다.

 

 

 퍼미션별로 가능한 연산을 하드코딩해 놓는다면, 해당 연산이 가능한 연산인지 판단하는 것은 매우 간단합니다.

 

 

 o가 쿼리로 들어온 연산을 의미합니다. permi_lo는 해당 유저가 몇 번째 숫자의 권한을 획득했는지 의미합니다. 소유자의 권한인 경우 0, 그룹 권한일 때에는 1을, 그 외의 경우에는 2가 들어옵니다. 파일 권한이 "643"이고 permi_lo가 2인 경우, f_permi[permi_lo]의 값은 "3"이 됩니다. 이제 permission["3"]에 쿼리로 들어온 연산이 있는지 판단하면 됩니다.

반응형

댓글을 달아 주세요