[프로그래머스]

프로그래머스 후보키 C++

Hevton 2023. 10. 5. 14:28
반응형

 

 

이번 문제는 카카오 blind 코딩테스트 문제이다.

오랜만에, 풀이하는데 정말 오랜 시간이 걸린 문제였다 ㅜ..ㅜ

 

문제의 핵심은 두가지이다.

 

1. 유일성

각 col을 뽑은 값이 tuple 내에서 유일해야한다

 

2. 최소성

각 col을 뽑은 것이 부분집합으로 존재하지 않는, 최소가 되어야 한다.

 

 

우선 내 처음 풀이는 일반적으로 내가 주로 사용하는 dfs 코드 방식의 풀이었다.

처음에는 맞추지조차 못했는데, 그 이유는 두가지였다.

 

1. 

먼저 일반적인 dfs 과정에서 0 1 2 3 4 를 순회한다고 보면

0 1 2 3 4 를 당연히 제일 먼저 순회하게 된다. 근데 난 여기서 이게 유일성이 된다면 곧바로 후보키에 넣었지만

이후에 탐색될 2 3 이나 2 4가 후보키라면, 0 1 2 3 4 는 후보키가 되어선 안된다. 이런 예외가 있었다.

따라서 dfs를 하면서 후보가 될 키들을 먼저 다 뽑아서 넣은 뒤에, 정렬을 통해 어떤 키부터 검증할지를 순서대로 해야한다.

 

2.

최소성 구현이 나에겐 너무 헷갈렸다. 최소성이란

만약 1 3 이라는 후보키가 정해졌을때, 1 2 3과 1 3 4 는 후보키가 되어서는 안된다.

하지만 단순 문자열 find로는 불가능한 것이, 134 에선 13을 찾을 수 있지만 123 에서는 13을 찾을 수 없기 때문이다.

따라서 문자열 내의 문자 각각 비교해줘야한다.

 

 

그렇게 해서 내가 처음 통과받은 풀이는 다음과 같다.

이 코드를 구현하면서 알게된 함수는 str.find() == string::npos 라는 문자∙문자열 찾기 함수!

C++에서는 contains가 없음을 주의한다.

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

using namespace std;

int R, C;
int candidateKey;
vector<int> colVector;
vector<string> candidateList;

int cmp(string& a, string& b) {
    return a.length() < b.length();
}

int diff(vector<vector<string>>& relation, string c) {
    
    set<string> s;
    
    for(auto r : relation) {
        
        string t = "";
        
        for(int i = 0; i < c.length(); i++) {
            t += r[c[i] - '0'];
        }
        
        s.insert(t);
    }
    
    return s.size();
}



void dfs(int index, vector<vector<string>>& relation) {
    
    if(colVector.size() > 0) {
        string s = "";
        for(auto x : colVector) s += to_string(x);
        candidateList.push_back(s);
    }
    
    for(int i = index; i < C; i++) {
        
        colVector.push_back(i);
        
        dfs(i + 1, relation);
        
        colVector.pop_back();
    }
}

int solution(vector<vector<string>> relation) {

    R = relation.size(); // 행의 수
    C = relation[0].size(); // 열의 수
    
    dfs(0, relation);
    
    sort(candidateList.begin(), candidateList.end(), cmp);

    vector<string> answer;
    
    for(auto candidate : candidateList) {
        
        if(diff(relation, candidate) == R) {
           
            bool unique = true;
            for(auto a : answer) {
                
                bool flag = true;
                for(int i = 0; i < a.length(); i++) {
                    
                    if(candidate.find(a[i]) == string::npos)
                        flag = false;
                }
                
                if(flag) {
                    unique = false;
                    break;
                }
            }
            if(unique) {
                answer.push_back(candidate);
            }
        }
    }

    return answer.size();
}

 

 

일반적인 dfs는 0 ~ 4까지를 뽑는다면

0 1 2 3 4 를 제일 먼저 들르게 되는데, 이 문제 특성상 0, 1, 2, 3, 4 순차적으로 작은 크기부터 들르는 과정이 필요했다.

순차성이 중요하다는 점에서 비트마스킹 풀이에 대한 관심을 갖게 되었다. 

 

그리고 비트마스킹으로 풀었다.

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

using namespace std;

vector<int> answer;

bool isUnique(int value) {
    
    for(auto a : answer) {
        // a & value == a 했더니 틀렸다. (a & value) == a 해야한다. 우선순위.
        if((a & value) == a)
            return false;
    }
    return true;
}

int solution(vector<vector<string>> relation) {
    
    int row = relation.size(); // row
    int col = relation[0].size(); // col
    
    /*
    if 컬럼이 4개라면 2^4 - 1 = 15 가지
    0001 : 1
    0010 : 2
    0011 : 3
    0100 : 4
    0101 : 5
    0110 : 6
    0111 : 7
    1000 : 8
    1001 : 9
    1010 : 10
    1011 : 11
    1100 : 12
    1101 : 13
    1110 : 14
    1111 : 15
    */
    
    // 1 << k 는 2의 k승을 의미한다.
    for(int i = 1; i < (1 << col); i++) {
        // 1 ~ 15 까지 dfs 과정이다.
        
        // 모든 튜플을 돌며 유일성이 되는지 체크
        set<string> s;
        for(int j = 0; j < row; j++) {
            
            string temp = "";
            for(int k = 0; k < col; k++) {
                
                if(i & (1 << k)) {
                    temp += relation[j][k];
                }
            }
            s.insert(temp);
        }
        
        if(s.size() == row && isUnique(i)) {
            answer.push_back(i);
        }
    }
    
    for(auto k : answer)
        cout << k << "\n";
    
    return answer.size();
}

코드에서 주의할 점은..

if(a & b == c) 같은 문제에서 b == c가 먼저 실행되기 때문에... a & b를 괄호로 싸줘야 한다!!!!

이거 때문에 조금 헤맸다.

 

 

 

다시 정리하면 오늘 알아야할 점은

 

1. find함수 (C++은 contains가 없다)

str.find(문자 또는 문자열) == string::npos

 

2. 비트연산자 &보다, 비교연산자 == 의 우선순위가 더 높다

 

3. 비트마스킹 풀이

1 << k 는2의 k 승을 의미한다.

 

 

 

참고

https://school.programmers.co.kr/questions/20888

https://hochoon-dev.tistory.com/entry/프로래머스-후보기-c

 

반응형