[프로그래머스] 후보키 C++ 풀이 및 해설

https://school.programmers.co.kr/learn/courses/30/lessons/42890

프로그래머스

 

풀이 방법

 

큰 틀에서 풀이 방법은 다음과 같다.

 

1. 컬럼들의 총 개수를 가지고 만들 수 있는 조합을 구한다. (총 개수가 4라면 0, 1, 2, 3, 01, 02, 03, ...) 01은 0번째 컬럼 1번째 컬럼을 뜻함.
2. 위에서 선택된 조합들을 가지고 컬럼값들을 모두 붙여본다. 붙여 만들어진 문자열이 기존에 만들어진 문자열이라면 유일성을 만족하지 않는것이다.
3. 유일성을 검사했으니 이제 최소성도 검사한다. 만들어진 문자열을 현재 존재하는 후보키 리스트와 비교한다. 이때 만들어진 문자열 또는 후보키 리스트의 후보키가 어느 한(만들어진 문자열, 후보키 리스트에 있는 문자열) 문자열에 포함되지 않는다면 유일성을 만족한다. => 왜냐 123을 후보키로 등록하려하니 12가 이미 존재한다면? 123에서 3을 빼도 유일성이 깨지지 않는다. 즉 최소성을 만족하지 않는다는 말임.

 

상세한 풀이 로직은 코드에 달린 주석을 확인하자!

 

아래는 여담이다.

 

그리고 최소성을 잘못 이해해서

(0),(2,3),(1,3,4)가 후보키가 되야 하는데 (2,3)을 후보키로 등록하고 앞으로 2 또는 3을 포함하는 후보키를 만들 수 없게 코드를 짰었다.

왜냐. 후보키가 포함하는 컬럼의 개수를 오름차순으로 처리하도록 코드를 짰기에

2와 3을 포함하는 최소성인 후보키는 (2,3)이며 2 또는 3은 이미 오름차순으로 처리하여 2 따로 3 따로는 후보키가 안되는걸 검증을 이미 한 상황이고.

2와 3을 묶어서 중복이 없고 최소가 되는 컬럼의 개수가 되는 상황이기에 2 또는 3을 포함하는 후보키는 더이상 만들 수 없다고 생각했다.

 

하지만.

(1,3,4)는 3을 포함하며 후보키가 될 수 있다.

후보키의 최소성은 하나의 컬럼을 제외하면 바로 유일성이 깨지는것임을 인지하자.

이것을 현재 등록된 후보키들과 현재 후보키로 등록하려고 선택된 컬럼들을 비교하여선택된 컬럼들이 현존하는 후보키에 포함되지 않는다면 후보키로 올려버리면 된다. (유일성을 만족한다는 전제에)

 

 

전체 코드

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

using namespace std;

bool comp(string a, string b) {
    if(a.size()<=b.size())
        return true;
    else
        return false;
}


void getComb(int startIdx, int maxIdx, string str, vector<string> &comb) {
        
    for(int i=startIdx; i<maxIdx; i++) {
        comb.push_back(str+to_string(i));
        getComb(i+1, maxIdx, str+to_string(i), comb);
    }
}


bool minTest(string a, string b) {
    // a가 b에 포함 안되는지 테스트
    // String.find()를 쓰면 테스트 18, 19, 20, 25, 28이 틀려버림
    int sameCnt = 0;
    for(int i=0; i<a.size(); i++) {
        for(int j=0; j<b.size(); j++) {
            if(a[i]==b[j]) {
                sameCnt++;
            }
        }
    }
    
    
    if(sameCnt==a.size() || sameCnt==b.size()) {
        return false;
    } else {
        return true;
    }
    
}
int solution(vector<vector<string>> relation) {
    int answer = 0;
    
    vector<string> keyList; // 후보키 저장소
    vector<string> comb; // 조합 저장소
    bool uniqFlag = true; // 유일성 만족 여부
    bool minFlag = true; // 최소성 만족 여부
    int maxIdx = relation[0].size(); // 컬럼의 개수(=탐색 가능한 컬럼의 최대 인덱스 0~(maxIdx-1)
    
    getComb(0, maxIdx, "", comb); // comb에 조합들 저장
    sort(comb.begin(), comb.end(), comp); // 적은 개수의 컬럼 조합들을 먼저 수행해줘야하기에 정렬 해줌.
    map<string, bool> m; // 선택된 컬럼값들을 모두 붙여 저장하는 저장소 (유일성 판별에 사용함)
    
    // 1. 조합을 가지고 모든 튜플들을 돌며 해당 컬럼들을 붙여 문자열을 만듬
    for(int i=0; i<comb.size(); i++) {
        string result=comb[i]; // 붙일 컬럼들을 나타내는 문자열
        
        for(int rowIdx=0; rowIdx<relation.size(); rowIdx++) { // 모든 튜플들에 대해 반복
            string str = ""; // 해당 튜플의 컬럼들을 붙인 문자열을 저장할 변수
            for(int colIdx=0; colIdx<result.size(); colIdx++) {
                str+=relation[rowIdx][result[colIdx]-'0']; // 해당 튜플의 컬럼값을 변수에 붙임
            }

            if(m.find(str) != m.end()) { // 이미 존재하는 문자열이라면
                uniqFlag=false;
                break;
            } else { // 새로운 문자열이라면
                m.insert({str, true});
            }
    }
        
        // (최소성)
        for(int idx=0; idx<keyList.size(); idx++) {
            
            // minTest: 두 문자열중 하나가 다른 문자열에 모두 포함되면 안되기에 검사함(최소성)
            if(!minTest(result, keyList[idx])) {
                minFlag = false;
                break;
            }
        }
                
                
        // 2. 최소성, 유일성 만족시 answer에 더함. 후보키 등록
        if(uniqFlag && minFlag) {
            keyList.push_back(result);
            answer++;
        }
        uniqFlag = true;
        minFlag = true;
        m.clear();
    }
    
    return answer;
}

 

 

 

예제1의 0과 1번째 컬럼을 붙인 문자열 상태 모습

 

 

주의!!

위의 테스트 케이스에서 0과 1번째 컬럼을 모두 써야 후보키가 될 수 있다.

그런데 컬럼값들을 붙여 만들어 유일성을 비교한다면

0과 1번째 컬럼을 붙인다면

aaa aaa aa 결과가 나온다.

aaa aaa가 겹쳐서 유일성을 만족하지 않는다고 나온다.

사실 (a aa)와 (aa a)로 구별이 가능한데 말이다.

 

컬럼 값들을 붙여 문자열을 만들때 컬럼 구분자도 같이 붙여주면 완벽한 코드가 된다.

 

질문게시판을 보며 찾은 저 테스트케이스를 통과하지 못해도 문제는 통과가 된다.

희한하다!