1062 가르침 (비트마스킹)

1062번: 가르침

1.접근

알파벳 소문자는 26개이다. 따라서 int(32bit) 크기의 2진수 배열에서 알파벳을 각각 하나씩 마스킹에 할당해서 문제를 풀 수 있다.

2.풀이

남극의 모든 단어는 a,n,t,i,c 으로 이루어져 있으므로 k가 5보다 작다면 어떠한 단어도 읽을 수 없다.

5개의 단어는 모두 배운다고 가정한고 한줄씩 입력받으면서 a,n,t,i,c을 지우고 가운데 알파벳들만 입력받는다. 만약 a,n,t,i,c로 지운 리스트의 길이가 0이라면 무조건 읽을 수 있는 단어이다.

그 후 비트마스킹에 활용하기위해 0~25사이의 숫자로 바꿔주는 과정을 거친다.

 

새로운 단어들의 집합에서 k-5개 만큼 itertools의 combinations를 사용해서 모든 케이스를 한 후 통과하는 단어의 최대값을 구한다.

 

여기서 가장 중요한 것은 읽을 수 있는 단어이냐 아니냐의 여부를 결정하는 알고있는 알파벳들과 주어진 단어의 비트 연산이다.

만약  4,5번째 알파벳을 배워서 11000(2)로 저장하고 주어진 단어는 2번쨰 4번째로 이루어진 01010(2)라고 생각해보자.  당연히 읽을 수 없는 단어일 것이다. 하지만 우리는 읽을 수 있는 단어를 판별해야 한다.

그에 따라서 생각해보면 배우지 않은 단어들과 배워야 하는 단어들이 겹치는 부분이 있을 때 배우지 못한다고 말할 수 있다. 어떻게 해야 할까?

 

답은 toggle(0과 1을 서로 바꾸는 것)하는 것이다.

(1<<26)-1의 값과 XOR연산을 한다면 모든 수는 토글 되어서 배우지 않은 단어가 1이 되고 배운 단어가 0이 될것이다. 따라서 주어진 단어와 &연산을 했을 때 0이 되면 겹치는 단어가 없다는 뜻으로 읽을 수 있다는 뜻이 된다. 그에 따라 최대값을 구해주면 된다.

주의해야 할 점은 k-5보다 num의 길이가 작다면 조합을 만들지 못하고 모두 읽을 수 있는 경우이다.

3.코드

4.배운점

• 비트마스킹을 어떻게 활용해야 할지 생각하기 힘들었는데 이 문제를 기점으로 감이 왔다. n이 32보다 작을 때 사용하기 편하다

• 비트마스킹 XOR 연산으로 0,1을 바꿀 수 있다. A를 토글하려면 A^(A<<n)-1 해버리자.