🔗 문제
https://school.programmers.co.kr/learn/courses/30/lessons/42890?language=python3
🕒 Python 풀이시간: 50분
from itertools import combinations
def solution(relation):
answer = 0
c=len(relation[0])
r=len(relation)
uniqueCase=set()
for j in range(1,c+1):
cases=list(combinations(range(c),j))
for case in cases:
keys=set()
for i in range(r):
oneKey=[]
for k in case:
oneKey.append(relation[i][k])
keys.add(tuple(oneKey))
if len(list(keys))==r:
minimality=True
for uc in list(uniqueCase):
all_include=True
for k in uc:
if k not in case:
all_include=False
break
if all_include:
minimality=False
break
if minimality:
uniqueCase.add(tuple(case))
answer+=1
return answer🕒 Java 풀이시간: 1시간
import java.util.*;
class Solution {
static public List<int[]> generateCombinations(int[] arr, int r) {
List<int[]> combinations = new ArrayList<>();
int[] combination = new int[r];
generateCombination(arr, combination, 0, 0, r, combinations);
return combinations;
}
static public void generateCombination(int[] arr, int[] combination, int start, int index, int r, List<int[]> combinations) {
if (index == r) {
combinations.add(combination.clone());
return;
}
for (int i = start; i <= arr.length - r + index; i++) {
combination[index] = arr[i];
generateCombination(arr, combination, i + 1, index + 1, r, combinations);
}
}
public int solution(String[][] relation) {
int answer = 0;
int c = relation[0].length;
int r = relation.length;
List<int[]> uniqueCases = new ArrayList<>();
int[] by_num_list = new int[c];
for (int i = 0; i < c; i++) {
by_num_list[i] = i;
}
for (int j = 1; j <= c; j++) {
List<int[]> cases = generateCombinations(by_num_list, j);
for (int[] cs : cases) {
HashSet<String> keys = new HashSet<>();
for (int i = 0; i < r; i++) {
StringBuilder oneKey = new StringBuilder();
for (int k : cs) {
oneKey.append(relation[i][k]).append(",");
}
keys.add(oneKey.toString());
}
if (keys.size() == r) { // 유일성 확인
boolean minimality = true;
for (int[] uc : uniqueCases) {
// 기존의 후보키가 현재 cs의 부분집합인지 확인
boolean isSubset = true;
for (int ucElem : uc) {
boolean found = false;
for (int cElem : cs) {
if (ucElem == cElem) {
found = true;
break;
}
}
if (!found) {
isSubset = false;
break;
}
}
if (isSubset) {
minimality = false;
break;
}
}
if (minimality) {
uniqueCases.add(cs);
answer++;
}
}
}
}
return answer;
}
}
🧩 최소성 개념 쉽게 이해하기!
최소성은 유일성을 보장하면서 다른 후보키의 부분집합이 되지 않는 것을 의미합니다. 예를 들어, [1,2,3]이라는 조합이 있을 때, [1,2]라는 조합이 이미 유일성을 보장한다면 [1,2,3]은 최소성을 위배한 것입니다.
🔄 모든 칼럼 조합 구하기: 조합 활용!
조합을 이용하여 가능한 모든 칼럼의 조합을 구했습니다. 이를 통해 후보키가 될 수 있는 모든 경우를 탐색할 수 있었습니다.
✅ 유일성 확인 방법: 집합으로 간단하게!
각 조합이 유일성을 보장하는지 확인하기 위해 집합을 사용했습니다. 집합의 크기와 행(row)의 수를 비교하여 겹치는 것이 존재하는지 판단할 수 있었습니다.
🔍 최소성 보장: 유일성 + 부분집합 체크!
유일성이 확인된 조합들 중에서 최소성을 보장하기 위해, 이미 확인된 조합이 현재 조합의 부분집합인지 체크했습니다. 이를 통해 최소성을 보장할 수 있었습니다.
이렇게 Python과 Java로 프로그래머스의 후보키 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
