후보키(2019 카카오 블라인드 채용)

문제 링크

코딩테스트 연습 - 후보키

 

 

풀이

주석으로 표시는 해놓았지만, 간단히 요약하자면 풀이는 다음과 같다.

 

next_permutation함수를 써서 처음에 column 개수로 '1'을 초기화한 후, 앞에서부터 '0'으로 바꾸어서 조합 조건을 만들어냈다.

 

즉, next_permutation을 do-while로 돌리면

첫 번째로 0111로 되면 0111, 1011, 1101, 1110 -> 총 4번(4C1)

두 번째로는 0011로 되면 0011, 0101, 0110, 1001, 1010, 1100 -> 총 6번(4C2)

...

마지막은 0000으로 do-while이므로 반복문을 한 번만 돌 것이다.

 

여기선 계속 해당 index까지 초기화대신 copy를 통해서 반복문을 돌렸다.

 

그 다음부터는

1) 최소성 판별(포함 관계 체크)

2) 유일성 판별(중복 체크)

을 하였고, 처음에는 몇 개가 실패가 뜨길래 확인해보았더니, string의 find() 함수를 쓴 것이 문제가 되었다.

 

예를 들면,

str1 = "abcd";

str2 = "ad"; 일때,

str2가 str1의 포함되는지 확인하려면 <algorithm>의 includes를 써야 한다.

 

ex 1) string::npos != str1.find(str2) -> false를 return 한다. (못 찾았다.)

- string::npos는 find() 함수가 못 찾을 시 리턴되는 값이다.

 

ex 2) includes(str1.begin(), str1.end(), str2.begin(), str2.end()) -> true를 리턴된다.(포함돼있다.)

- a, d를 부분집합으로 보고 포함 여부를 찾기 때문에 true가 리턴된다.

 

유일성 판별은 multiset 컨테이너를 사용하였고, 중복 여부를 판별하기 위해 이어붙인 string을 insert() 하면서 그 string의 count가 1이 아니면 중복 값이 있는 것으로 처리하였다.

 

간단히 요약한다해놓고...

 

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(vector<vector<string>> relation) {
    int answer = 0;
    int col = relation[0].size();
    int row = relation.size();
    
    vector<string> again;       // 최소성 판별용
    string combi(col, '1');
    for(int a=0; a<col; a++){
        combi[a] = '0';
        string copy(combi);
        
        // 조합
        do{
            bool isCandidate = true;
            multiset<string> sub_set;    // 유일성 판별용
            string index;           // 최소성 판별용
            // 선처리('0'인 것의 index)
            for(int i=0; i<col; i++){
                if(copy[i] == '0'){
                    index += to_string(i);
                }
            }
            
            // 최소성 판별
            for(string s: again){
                if(includes(index.begin(), index.end(), s.begin(), s.end())){
                    isCandidate = false;
                    break;
                }
            }
            if(!isCandidate) continue;          // 탈락
            
            // 유일성 판별(string 이어붙여서 중복성 체크)
            for(int i=0; i<row; i++){
                string s = "";
                for(char c : index){
                    int j = c - '0';
                    s += relation[i][j];
                }
                sub_set.insert(s);
                if(sub_set.count(s) != 1){
                    isCandidate = false;
                    break;
                }
            }
            if(!isCandidate) continue;      // 탈락
            
            again.push_back(index);         // 최소성 판별용
        }while(next_permutation(copy.begin(), copy.end())) ;
    }
    answer = again.size();
    return answer;
}