인프런 커뮤니티 질문&답변

답변 주셔서 감사합니다!

문제의 조건이 'a', 't', 'n', 'c', 'i'를 무조건 배워야하는 문자에 포함시켜야하기 때문에, 비트의 개수인 oneCount가 K-5인 경우만 체크하도록 하였습니다.

if(oneCnt != K - 5) // K - 5개를 뽑은 경우만 체크합니다.

continue;

- 왜 굳이? / 이부분 왜 체크하나요?

>> 배울 수 있는 글자의 수보다 더 적게 뽑힌 경우 또는 많이 뽑힌 경우를 제외하기 위해서 추가했습니다.

K : 7,

모든 남극 문자에서 나온 글자의 수 : 10

이 상황에서 K는 'a', 't', 'n', 'c', 'i'을 무조건 배워야하기 때문에 이를 제외하면 2개(K-5)를 배울 수 있습니다.

alpabat 벡터에는 'a', 't', 'n', 'c', 'i'을 제외한 5개의 문자가 들어가게됩니다.

=> 5개 중에 2개를 뽑는 경우의 수를 체크하여, 읽을 수 있는 남극 문자의 수를 구합니다.

=> alpabat.size()에서 K - 5개를 뽑는 경우의 수를 체크하여, 읽을 수 있는 남극 문자의 수를 구합니다.

이렇게 생각했습니다!

for(int i = 1; i < (int)pow(2, alpabat.size()); i++) // alpabat으로 만들 수 있는 모든 조합을 체크합니다.
{                                                    // alpabat.size()가 5라면, 00001 ~ 11111을 체크합니다.
     int oneCnt = 0; // 1인 비트의 개수
     int cnt = 0; // 각 경우의 읽을 수 있는 남극 문자의 개수 
     int word = 0; // i번째 경우의 수의 읽을 수 있는 글자를 비트로 표현한 것

     for(int j = 0; j < alpabat.size(); j++) // 각 비트를 체크합니다.
     {
         if(i & (1 << j)) // 해당 비트가 1이라면?
         {
             word |= (1 << (alpabat[j] - 'a')); // alpabat의 j 인덱스에 저장된 글자를 word에 저장합니다.
             oneCnt++; // 나온 1의 개수를 증가시킵니다.
             if(oneCnt > K - 5) // oneCnt가 배울 수 있는 글자의 수를 초과하면 break합니다.
                 break;
         }
     }
        
     if(oneCnt != K - 5) // K - 5개를 뽑은 경우만 체크합니다.배울 수 있는 글자의 수보다 적게 배우거나 많이 배운 경우를 제외합니다.
        continue;
        ---생략---
}