(Java) 프로그래머스 - 후보키

카카오 문제 치고 문제 설명이 짧아서 쉽게 풀 수 있을 줄 알았는데 꽤나 오래 걸렸다.

데이터 베이스를 공부한 지 오래되어서 후보키의 개념이 생각나지 않았지만

문제 설명을 보고 빠르게 이해했다.

 

처음에는 먼저 컬럼을 탐색해서 중복이 없다면 조합을 만드는 로직으로 생각했으나

그게 더 복잡한 것 같아서 모든 조합을 만들고 유일성과 최소성을 검사하는 로직으로 구현했다.

매끄럽게 풀었던 문제가 아니라서 조금 찝찝한 느낌이 있다. 기억이 나지 않을 때쯤 다시 풀어봐야겠다.

---

최종 코드

import java.util.*;
class Solution {
    static int answer;
    static int n,m;
    static List<HashSet<Integer>> candidateKey;
    static String[][] relationCopy;
    public int solution(String[][] relation) {
        relationCopy = relation;
        
        answer = 0;

        // 중복 조합을 고려하여 HashSet 사용
        candidateKey = new ArrayList<>();
        n = relationCopy.length;
        m = relationCopy[0].length;

        // 1부터 m까지 사이즈만큼 조합 생성하기
        for (int i = 1; i < m + 1; i++) {
            combination(0, i, 0, new HashSet<>());
        }

        return answer;
    }
    // 조합 생성 메서드
    static void combination(int idx, int size, int depth, HashSet<Integer> set) {
        // 조합이 만들어지면
        if(depth == size) {
            // 유일성 검사
            if(!unique(set)) {
                return;
            }
            // 최소성 검사
            for (HashSet<Integer> key : candidateKey) {
                if(set.containsAll(key)) {
                    return;
                }
            }
            // 조합을 추가하고 answer 증가
            candidateKey.add(set);
            answer++;
            return;
        }
        // 조합 만들기
        for (int i = idx; i < m; i++) {
            HashSet<Integer> newSet = new HashSet<>(set);
            newSet.add(i);
            idx++;
            combination(idx, size, depth + 1, newSet);
        }
    }
    // 유일성 검사 메서드
    static boolean unique(HashSet<Integer> set) {
        List<String> list = new ArrayList<>();
        // 만들어진 조합으로 중복되는지 검사
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int idx : set) {
                sb.append(relationCopy[i][idx]);
            }
            if(!list.contains(sb.toString())) {
                list.add(sb.toString());
            } else {
                return false;
            }
        }
        return true;
    }
}