나의 논리

가르침
힘들게 푼 문제이다. 비트마스크를 이용해서 풀었는데 비트마스크 사용법이 익숙하지 않아서 사소한 실수로 인해 많은 시간이 걸렸었다.

우선 코드를 보자

총 26개의 알파벳을 가지고 k가지를 선택하여 경우의 수를 만드는 문제이다.
모든 비트가 0일때 k번째 자리에 대해 (1<<K) or 연산을 하면 k번째 자리에 비트 1을 킨다.
& ~( 1<<k)를 하면 비트 1인 끈다.

anta,tica는 무조건 포함하므로 저 두 문자열들이 공통으로 가지는 문자들은 무조건 포함해야한다.
그래서 먼저 모든 비트가 0인 mask라는 변수를 선언하여 anta,tica에 포함된 알파벳의 비트를 킨다.
mask |= (1<<문자 – ‘a’)

1~ (1<<26)가지의 경우의 수 중 bit인 경우의 수가 bit & mask == mask라면 bit는 mask에 포함된 알파벳들을 모두 포함한다는 뜻이다. 그리고 아래로 내려와

int cnt=0;
            for(int i=0; i<26; ++i){
                if(bit & (1<<i)) cnt += 1;
            }
            if(cnt != k ) continue;

이 코드에서 발생한 실수 때문에 가장 시간을 많이 허비했다.
bit에 켜진 알파벳은 k개이어야 하기 때문에 비트 1의 갯수를 세는 로직인데 bit가 1부터 시작하는것과
비트를 시프트 ( 1 << i) 하는것을 햇갈려서 비트 시프트를 1부터 ( for (int i=1; …) 시작해서 계속 코드를 돌렸었다.

비트를 1부터 시작하는것, (for (int bit = 1… )) 는 bit가 0인 경우 , 모든 비트가 0으로 설정이 되어 있는데 이 경우는 k < 5 || k == 26 경우에서 처리된다. k == 0인 경우 는 bit == 0일때다 그 외에는 bit는 1이상이다.

bit가 있는 for문을 돌릴때는 5<= k <26이기 때문에 bit는 1이상이어야해서 bit의 시작을 1로 했다.
그리고 쓰다보니 bit = 0인 경우는 없다고 생각했었는데 0이어도 상관없을것 같다. 오히려 0인 경우가 k==0인 경우이니 if문을 통해 에러 처리를 하지 않았다면 아마 k==0인 경우에 bit = 1부터 시작하니 예제 코드가 맞더라도 코드를 제출 했을때는 오답처리 났을거다.

아무튼 bit=1로 시작을 하다보니 실수로 비트 시프트를 하는것도 1 << 1부터 시작을 해버렸다.
(1<<0)은 비트 1을 시프트 하지 않고 1의 자리에 위치 시킨다는 뜻이고, 이 문제에서는 첫번째 비트가 켜져있는지 카운트하는 로직이다.

첫번째 비트를 카운트하지 않은 대신에 다른 비트를 카운트하는 바람에 마지막 예제에서 정답이 계속 4가 나왔다. 즉 k개 카운트해야하는데 실질적으로 k+1개 카운트 한것이다.

그래서 비트를 (1<<i) 부분에서 i가 0부터 시작하도록 디버깅을 했고 그 결과 정답처리가 되었다.