[프로그래머스/자바] 후보키 풀이 - 2019 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2019 KAKAO BLIND RECRUITMENT Level 2 문제다.

 

 

접근 -> 백트래킹, HashSet, 구현

 

 

알고리즘 순서

1. DFS로 가능한 모든 애트리뷰트의 조합을 구한다.

2. 조합할 때마다 그 애트리뷰트의 조합이 유일성을 만족하는지 판별한다. 만족한다면 uniKey list에 넣는다.

3. uniKey에 들어있는 애트리뷰트 조합을 하나씩 꺼내 최소성을 만족하는지 판별한다. 만족한다면 cdKey list에 넣는다.

4. cdKey에는 유일성, 최소성을 모두 만족하는 키가 저장되어 있으므로 cdKey list의 size를 반환한다.

 

 

 

1.

DFS를 계속 돌다가 애트리뷰트의 갯수보다 더 깊어지면 ArrayIndexOutOfBoundsException 예외가 발생하므로 

깊이가 1~애트리뷰트인 경우만 DFS를 진행한다.

애트리뷰트를 조합하기 위해 애트리뷰트 인덱스를 문자열 형식으로 append한다.

즉, 문제의 입출력 예시 처럼 애트리뷰트가 4개인 경우

깊이가 1인 애트리뷰트 조합은 0, 1, 2, 3이고

깊이가 2인 애트리뷰트 조합은 01, 02, 03, 04, 12, 13, 23이고

깊이가 3인 애트리뷰트 조합은 012, 013, 014, 123 등이 된다.

 

 

2. 

DFS를 통해 애트리뷰트를 조합할 때마다 isUnique 함수에 그 조합을 전달해서 유일성을 만족시키는지 판별한다.

애트리뷰트 조합에 맞는 모든 문자열을 합치고 map에 넣는다.

이때 key는 애트리뷰트 조합에 맞는 문자열이고, value는 그 문자열이 나타난 횟수이다.

애트리뷰트 조합이 유일성을 가진다면 map에 있는 모든 문자열이 한 번씩만 나타나야한다.

 

만약 2번 이상 나타난다면 유일성을 만족하지 않는 것이므로 false를 반환한다.

예를 들어 여기서 애트리뷰트 조합이 학번(0)인 경우

map에는 (100, 1), (200, 1), (300, 1), (400, 1), (500, 1), (600, 1)이 들어갈 것이다.

모든 문자열이 한 번씩만 나타나므로 해당 조합은 유일성을 만족한다.

 

하지만 애트리뷰트 조합이 전공, 학년(23)인 경우

map에는 (music2, 2), (math2, 1), (computer3, 1), (computer1, 1), (music3, 1)이 된다.

이 때 music2가 2번 나타났으므로 유일성을 만족하지 않는다.

 

isUnique가 true인 경우만 uniKey에 넣는다.

즉 uniKey에는 유일성을 만족하는 모든 애트리뷰트 조합이 저장되어 있다.

 

 

3.

uniKey에 들어있는 애트리뷰트 조합을 isMin에 전달해 최소성을 만족하는지 판별한다.

전달된 애트리뷰트 조합이 이미 cdKey(후보키)에 포함되어 있다면 최소성을 만족하지 않는 것이므로 false를 반환한다.

 

예를 들어 애트리뷰트 조합이 024이고 cdKey에 04와 1이라는 조합이 저장되어 있다면,

04가 024에 포함되어 있으므로 024는 최소성을 만족하지 않는다.

 

이를 구현하기 위해서 isMin의 매개변수로 전달된 024를 하나하나씩 쪼개 HashSet에 저장한다. (0, 2, 4)

그리고 cdKey에 있는 키를 하나하나씩 (0, 4 / 1)꺼내 HashSet에 포함되어 있는지 확인한다.

만약 cdKey의 모든 원소가 HashSet에 포함되어 있는 키가 하나라도 있다면 false를 반환한다.

 

isMin이 true인 경우에만 cdKey에 넣는다.

 

 

 

4.

cdKey에는 유일성, 최소성을 모두 만족하는 키가 저장되어 있으므로 cdKey list의 size를 반환하면

문제가 요구하는 후보키의 개수가 된다.

 

 

 

 

배운점 및 느낀점

개인적으로 되게 재밌게 푼 문제다.

다만 코드도 길고 복잡하게 푼 것 같다.

튜플 수와 애트리뷰트 수의 최대(8)가 크지 않아서 맞았지만,

애트리뷰트 수가 조금만 더 커지면 시간이 안 나올 것 같다..

 

 

import java.util.*;

class Solution {
    static ArrayList<String> uniKey = new ArrayList<>();
    static ArrayList<String> cdKey = new ArrayList<>();
    static int n, m;
    static boolean[] visit;
    static String[][] rel;

    public int solution(String[][] relation) { 
        n = relation.length; // 튜플 개수
        m = relation[0].length; // 애트리뷰트 개수

        visit = new boolean[m];
        rel = relation;

        DFS(0, new StringBuilder());

        uniKey.sort((o1, o2) -> o1.length() == o2.length() ? 
                o1.compareTo(o2) : o1.length() - o2.length());

        // 유일성을 만족하는 키 중 최소성을 만족하는 키를 list에 추가
        for(int i=0;i<uniKey.size();i++)
            if(isMin(i))
                cdKey.add(uniKey.get(i));

        return cdKey.size();
    }

    static void DFS(int start, StringBuilder sb) {
        for(int i=start;i<m;i++) {
            if(!visit[i]) {
                visit[i] = true;
                sb.append(i);

                String tuple = sb.toString();
                // 유일성을 만족한다면 list에 추가
                if(isUnique(tuple))
                    uniKey.add(tuple);

                if(i + 1 != m)
                    DFS(i + 1, sb);
                visit[i] = false;
                sb.setLength(sb.length() - 1);
            }
        }
    }

    static boolean isMin(int idx) {
        String target = uniKey.get(idx);
        HashSet<Integer> set = new HashSet<>();

        for(char c : target.toCharArray())
            set.add(c - '0');

        // 검사하려는 키가 후보키를 포함한다면 유일성을 만족하지 못함
        for(String s : cdKey) {
            int check = 0;
            for(char c : s.toCharArray()) {
                int i = c - '0';
                if(!set.contains(i))
                    break;
                check++;
            }
            if(check == s.length())
                return false;
        }

        return true;
    }

    static boolean isUnique(String s) {
        // 문자열, 출현 개수
        HashMap<String, Integer> map = new HashMap<>();

        for(int i=0;i<n;i++) {
            StringBuilder sb = new StringBuilder();
            for(char c : s.toCharArray()) {
                sb.append(rel[i][c - '0']);
            }
            String tuple = sb.toString();
            map.put(tuple, map.getOrDefault(tuple, 0) + 1);
        }

        // 개수 둘 이상이라면 유일하지 않은 것
        for(int i : map.values())
            if(i > 1) return false;

        return true;
    }
}