[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 후보키

후보키

문제

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

입출력 예

 

제한사항

• relation은 2차원 문자열 배열이다.
• relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
• relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
• relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
• relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

 

문제 분석

• 후보키 : 릴레이션의 튜플을 유일하게 식별할 수 있는 속성 또는 속성의 집합으로 유일성과 최소성을 만족함

• 입력 : 릴레이션

• 출력 : 후보키의 최대 개수

 

아이디어

어떤 속성이나 속성의 조합이 유일성을 만족하는지 알 수 없기 때문에 모든 경우를 시도해봐야 한다. 만약 어떤 조합으로 튜플 개수를 세었을 때 중복이 존재하지 않는다면, 그 조합은 유일성을 만족한다고 볼 수 있다. 또한 최소성을 확인하기 위해, 현재 속성 조합에서 특정 속성을 제거해도 유일성이 유지되는지 검토해야 한다.

 

접근 방법

1. 알고리즘 선택: 완전 탐색과 조합을 활용

모든 가능한 조합을 생성하고 ➡️ 그중에서 최소성과 유일성을 만족하는 조합만을 반환할 계획이다.

 

2. 시간 복잡도: O(2^m)

조합 생성 부분 (열이 m개인 경우): O(2^m)

최소성을 확인하고 유일성을 검사하는 부분 (각 튜플에 대해 진행): O(n)

이 문제에서 m은 최대 20이므로, 시간 복잡도는 O(2^20)이다. 2^20은 10^8보다 훨씬 작기 때문에 해당 접근 방식으로 구현하는 것이 가능하다고 판단 후 코드 구현에 들어갔다.

 

코드 구현

1. 실패 코드

public class CandidateKey {
    public int solution(String[][] relation) {
        List<Set<Integer>> candidateKeys = new ArrayList<>();
        int rowLen = relation.length;
        int colLen = relation[0].length;

        for(int length=1; length<=colLen; length++){
            List<Set<Integer>> combinations = new ArrayList<>();
            getCombinations(0,0, length, combinations, new HashSet<>(), colLen);

            for(Set<Integer> cols : combinations){
                boolean minimality = true;

                for(Set<Integer> key : candidateKeys){
                    // 이 부분
                    if(key.containsAll(cols)){
                        minimality = false;
                        break;
                    }
                }

                if(!minimality){
                    continue;
                }

                Set<String> rowSet = new HashSet<>();
                for(String[] row : relation){
                    StringBuilder rowStr = new StringBuilder();
                    for(int col : cols){
                        rowStr.append(row[col]);
                    }
                    rowSet.add(rowStr.toString());
                }

                if(rowSet.size() == rowLen){
                    candidateKeys.add(new HashSet<>(cols));
                }
            }
        }

        return candidateKeys.size();
    }

    public void getCombinations(int start, int depth, int maxDepth,
                                List<Set<Integer>> combinations, Set<Integer> curr,
                                int colLen){

        if(depth == maxDepth){
            combinations.add(new HashSet<>(curr));
            return;
        }

        for(int i = start; i < colLen; i++){
            curr.add(i);
            getCombinations(i + 1, depth + 1, maxDepth, combinations, curr, colLen);
            curr.remove(i);
        }
    }

}

 

이유 : 최소성 검사에서는 key가 cols를 포함하는 것이 아니라, 
cols가 key를 포함하는지 확인해야 한다.

key.containsAll(cols) -> cols.containsAll(key)

 

추가적으로 메서드 분리 적용해보았다.

 

2. 성공 코드

import java.util.*;

public class CandidateKey {
    public int solution(String[][] relation) {
        // 최종 후보 키를 저장할 리스트: 조합 + 최소성 + 유일성 만족
        List<Set<Integer>> candidateKeys = new ArrayList<>();

        // 릴레이션의 행 수
        int rowLen = relation.length;
        // 릴레이션의 열 수
        int colLen = relation[0].length;

        for (int length = 1; length <= colLen; length++) {
            List<Set<Integer>> combinations = new ArrayList<>();

            // 1. 모든 속성 조합을 생성하는 메서드 호출
            getCombinations(0, 0, length, combinations, new HashSet<>(), colLen);

            // 2. 생성된 모든 조합에 대해 최소성과 유일성 검사 시작
            // 2-1. 최소성 검사
            isMinimality(combinations, candidateKeys, relation, rowLen);
        }
        // 후보 키의 개수를 반환
        return candidateKeys.size();
    }

    // 모든 속성 조합을 생성하는 메서드
    public void getCombinations(int start, int depth, int maxDepth,
                                List<Set<Integer>> combinations, Set<Integer> curr,
                                int colLen) {

        // 현재 조합의 길이가 최대 길이(maxDepth)에 도달하면, 해당 조합을 리스트에 추가하고 종료
        if (depth == maxDepth) {
            combinations.add(new HashSet<>(curr));
            return;
        }

        for (int i = start; i < colLen; i++) {
            curr.add(i);
            getCombinations(i + 1, depth + 1, maxDepth, combinations, curr, colLen);
            curr.remove(i);
        }
    }

    // 최소성 검사 메서드
    public void isMinimality(List<Set<Integer>> combinations, List<Set<Integer>> candidateKeys,
                             String[][] relation, int rowLen) {
        for (Set<Integer> cols : combinations) {
            boolean minimality = true;

            // 기존 후보 키들과 비교하여 현재 조합이 최소성을 만족하는지 검사
            for (Set<Integer> key : candidateKeys) {
                // 만약 현재 조합이 기존 후보 키의 부분집합이라면, 최소성 위배
                if (cols.containsAll(key)) {
                    minimality = false;
                    break; // 최소성을 만족하지 않으므로 더 이상 검사할 필요 없음
                }
            }

            // 최소성을 만족할 경우에만 유일성 검사로 넘어감
            if (minimality) {
                // 2-2. 유일성 검사
                isUniqueness(relation, cols, rowLen, candidateKeys);
            }
        }
    }

    // 유일성 검사 메서드
    public void isUniqueness(String[][] relation, Set<Integer> cols,
                             int rowLen, List<Set<Integer>> candidateKeys) {
        Set<String> rowSet = new HashSet<>();
        for (String[] row : relation) {
            StringBuilder rowStr = new StringBuilder();
            for (int col : cols) {
                rowStr.append(row[col]);
            }
            // 각 행의 속성 조합 값으로 구성된 문자열 추가
            rowSet.add(rowStr.toString());
        }

        // rowSet의 크기가 행의 수와 같다면, 모든 행이 유일함을 의미
        if (rowSet.size() == rowLen) {
            candidateKeys.add(new HashSet<>(cols));
        }
    }
}

정확성: 100.0

합계: 100.0 / 100.0

 

회고

간단한 완전탐색 문제를 풀다가 오늘 푼 문제는 좀 어려웠다. 해결하는 데 3시간 정도 걸렸는데, 나중에 다시 돌아와서 풀어봐야겠다는 생각이 들었다. 유일성과 최소성의 개념은 알고 있었지만 이를 코드로 구현하려면 무엇을 어떻게 확인해야 하는지 꼼꼼히 따져야 했는데, 덕분에 코드 구현 능력이 +1 향상된 것 같아 뿌듯했다. 완전탐색 문제를 좀 더 풀어보면 감이 잡힐 것 같아 앞으로도 꾸준히 문제를 풀어볼 생각이다😀