프로그래머스 Lv.2) 후보키

2019 KAKAO BLIND RECRUITMENT

후보키

코딩테스트 연습 - 후보키

풀이

정말 어려웠다. 매우매우 복잡한 문제였다. 이 문제가 레벨 2라는 것에 의문이 들었다...

처음에는 단일 애트리뷰트가 후보키가 되는 경우를 저장하고, 이 경우를 제외하고 키를 두개부터 row의 수만큼 순열을 구해 가장 작은 자리 수 까지만 후보키를 구하려고 했다. 하지만, 위의 로직이 애트리뷰트 갯수가 2에서 끝났다고 치면, 3개인 경우를 체크하지 못한다는 단점이 있었다. 그래서 그냥 문제 해설을 보기로 했다. 카카오 측에서 원하는(?) 풀이 방법은 슈퍼키를 모두 구하고 슈퍼키가 후보키가 될 수 있는 지 체크하는 방식이었다. 그래서 이대로 문제를 풀어봤는데 너무 오래걸리고 복잡했다.

 

로직

1. 가능한 모든 순열을 구한다.

2. 순열에 따라 슈퍼키가 되는 애트리뷰트 조합을 구해 keyList에 저장한다.

 2-1. 2중 for문을 통해 슈퍼키가 희소성을 만족하는지 확인한다.

 2-2. 희소성에 만족하지 못하면 슈퍼키에서 제거한다.

3. 슈퍼키를 돌면서 후보키가 되는지 안되는지 확인한다.

 3-1. 2중 for문을 통해 현재의 슈퍼키가 최소성을 만족하는지 확인한다.

 3-2. 최소성을 만족하지 못하면 해당 슈퍼키를 삭제한다.

4. 위의 로직을 거쳐 남은 keyList(후보키)의 사이즈를 리턴한다.

 

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

다중 for문이 가능했던 것은 위의 조건에 컬럼과 로우가 짧기 때문이다. 왠만하면 지양하고 싶은데, 이 문제에서는 어떻게 해야하는지 감이 안와서 다중 for문을 이용했다.

 

코드

import java.util.ArrayList;
import java.util.LinkedList;

class Solution {
    static ArrayList<int[]> keyList;
    public int solution(String[][] relation) {  // column : 행 , row : 열
        keyList = new ArrayList<>();
        // 모든 조합 만들기
        for(int i=1; i<=relation[0].length; i++) {  // 1개 ~ n개
            combination(0, i, new int[relation[0].length], new LinkedList<Integer>(), relation);
        }

        // superkey 조합 만들기
        getSuperKeys(relation);

        // 후보키가 아닌 슈퍼키 제거
        if(keyList.size() >1) {
            for(int i=1; i<keyList.size(); i++) {
                int[] originArr = keyList.get(i);
                for(int j=i-1; j>=0; j--) {
                    int[] targetArr = keyList.get(j);
                    int cnt =0;
                    for(int origin : originArr) {
                        for(int target : targetArr) {
                            if(target == origin) {
                                cnt++;
                            }
                        }
                    }
                    // 삭제
                    if(cnt == targetArr.length) {
                        keyList.remove(i--);
                        break;
                    }
                }
            }
        }

        return keyList.size();
    }
    
    private void getSuperKeys(String[][] relation) { // 슈퍼키 아닌 키 제거
        for(int i=0; i<keyList.size(); i++) {
            int[] keyArr = keyList.get(i); // 키 조합
            loop:
            for(int col=0; col<relation.length-1; col++) {
                for(int find =col+1; find<relation.length; find++) {
                    boolean isContain = true;
                    for(int idx =0; idx<keyArr.length; idx++) {
                        if(!relation[col][keyArr[idx]].equals(relation[find][keyArr[idx]])) {
                            isContain = false;
                            break;
                        }
                    }
                    if(isContain) { // 모든 정보에 대해 이미 가지고 있으면
                        keyList.remove(i--); // 삭제
                        break loop;
                    }
                }
            }
        }
    }

    private void combination(int idx, int limit, int[] visit, LinkedList<Integer> list, String[][] relation) {
        if(list.size() == limit) {
            int[] tmp = new int[limit];
            for(int i=0; i<limit; i++) {
                tmp[i] = list.get(i);
            }
            keyList.add(tmp);
            return;
        }

        for(int i=idx; i<visit.length; i++) {
            if(visit[i] ==0 && !keyList.contains(i)) {
                visit[i] =1;
                list.offer(i);
                combination(i+1, limit, visit, list, relation);
                list.pollLast();
                visit[i] =0;
            }
        }
    }
}