후보키

코딩테스트 연습 - 후보키 | 프로그래머스 (programmers.co.kr)

1. 문제이해

1.1. 문제 출제 의도 파악하기

• 만들 수 있는 모든 열 조합에 대해 유일성과 최소성을 검사하는 문제입니다.
  • 학번, 이름을 고르는 것과 이름, 학번을 고르는 것은 동일하므로 순열 문제가 아니라 조합 문제입니다.
• 조합을 구하는 방법을 알고있는지 물어보는 문제입니다.

1.2. 문제 해결하기

• 유일성을 검사하는 방법은 다음과 같습니다.
  • n개의 열을 선택합니다.
  • 모든 행에 대해 임의의 두 행이 선택한 n개의 열이 같으면 유일성을 위반합니다.
• 최소성을 검사하는 방법은 다음과 같습니다.
  • 어떤 n개의 열 조합이 유일성을 만족할 때, 해당 조합 내에 다른 후보키가 있으면 최소성을 위반합니다.
  • 예를 들어, 1, 3이라는 후보키가 있다면, 1, 2, 3번 열 조합이 유일성을 만족하더라도 최소성을 위반하므로 후보키가 될 수 없습니다.

2. 문제풀이

2.1. 코드 설명하기

1. 조합 구하기

for (int i = 1; i <= col; ++i) {
    // col개의 공간을 true로 초기화하고 앞에서부터 i개를 false로 초기화.
    vector<bool> comb(col, true);
    for (int j = 0; j < i; ++j) comb[j] = false;
    // 조합을 구한다.
    do {
        /* ... */
    } while(next_permutation(begin(comb), end(comb)));
}

• 이 문제에서는 선택해야 하는 열의 개수가 1개 → 2개 → … → 컬럼(column)개로 늘어나므로 바깥쪽 for문이 필요합니다.
• 내부에서는 조합을 구하기 위해 선택해야하는 열의 개수만큼 앞에서부터 0인 배열을 만듭니다. (01111, 00111 같이)

2. 유일성 검사하기

bool checkUniqueness(const vector<vector<string>>& relation, const vector<int>& cols, int row) {
	for (int i = 0; i < row; ++i)
		for (int j = i + 1; j < row; ++j) {
			int cnt = 0;
			for (const int& col : cols)
				if (relation[i][col] == relation[j][col]) cnt++;
			if (cnt == cols.size()) return false;
		}
	return true;
}

• i와 j, 이중 반복문을 이용해서 모든 tuple에 대해 유일성을 검사합니다.
• 서로 다른 두 tuple에 대해 선택한 열을 비교해서 같은 열이 있다면 카운팅합니다.
• 카운팅한 숫자가 선택한 열의 개수와 같다는 것은 두 tuple이 동일하다는 의미이므로 유일성을 위반한다고 판단합니다.
• 보다 더 나은 방법이 있다면 좋을탠데, 당장 떠오르는 방법이 이것밖에 없어서 이렇게 구현했습니다.

3. 최소성 검사하기

bool checkMinimality(const vector<int>& cols, const vector<vector<int>>& cands) {
	for (const vector<int>& cand : cands) {
		int cnt = 0;
		for (const int& c : cand)
			if (find(begin(cols), end(cols), c) != end(cols)) cnt++;
		if (cnt == cand.size()) return false;
	}
	return true;
}

• 유일성을 만족하는 어떤 열의 조합이 최소성을 만족하기 위해서는 후보키를 포함해서는 안됩니다.
• 현재 열 조합에 후보키가 포함되는지를 카운팅을 통해 검사합니다.
• 보다 더 나은 방법이 있다면 좋을탠데, 당장 떠오르는 방법이 이것밖에 없어서 이렇게 구현했습니다.

2.2. 시간/공간복잡도 계산하기

선택해야하는 열의 개수가 증가하므로 바깥 for문을 사용함 = n

내부에서 조합을 구함 = $n!$

∴ $O(n \times n!) = O((n + 1)!) = 9! = 362,880$

2.3. 전체코드

#include <vector>
#include <algorithm>
using namespace std;

// 최소성 검사, 후보키 조합이 포함된 조합은 최소성을 만족하지 않는다. (e.g. {1, 2}가 후보키면 {1, 2, n}은 불가)
bool checkMinimality(const vector<int>& cols, const vector<vector<int>>& cands) {
    for (const vector<int>& cand : cands) {
        int cnt = 0;
        for (const int& c : cand)
            if (find(begin(cols), end(cols), c) != end(cols)) cnt++;
        if (cnt == cand.size()) return false;
    }
    return true;
}

// 유일성 검사. 선택된 모든 열에 대해 튜플값이 동일하면 유일성을 만족하지 않는다.
bool checkUniqueness(const vector<vector<string>>& relation, const vector<int>& cols, int row) {
    for (int i = 0; i < row; ++i)
        for (int j = i + 1; j < row; ++j) {
            int cnt = 0;
            for (const int& col : cols)
                if (relation[i][col] == relation[j][col]) cnt++;
            if (cnt == cols.size()) return false;
        }
    return true;
}

int solution(vector<vector<string>> relation) {
    int row = relation.size(), col = relation[0].size();
    vector<vector<int>> candidateKey;

    for (int i = 1; i <= col; ++i) {    // 선택할 attributes(열)의 개수
        // 조합을 구할 때 사용할 배열 초기화
        vector<int> comb(col, 1);
        for (int j = 0; j < i; ++j) comb[j] = 0;

        do {
            // 선택된 열의 조합을 추출한다.
            vector<int> selectedCols;
            for (int j = 0; j < col; ++j) if (comb[j] == 0) selectedCols.push_back(j);

            // 유일성과 최소성을 검사한 뒤 통과한 조합은 후보키로 저장한다.
            if (checkUniqueness(relation, selectedCols, row) == false) continue;
            if (checkMinimality(selectedCols, candidateKey) == false) continue;
            candidateKey.push_back(selectedCols);
        } while(next_permutation(begin(comb), end(comb)));
    }
    return candidateKey.size();
}