[ 프로그래머스 Lv.2 - 후보키 ]

### 문제 분석

문제 유형

문제유형은 사실 어느 한 알고리즘을 알아야 풀 수 있는 문제라기 보다는 복합적인 구현능력을 묻는 문제였다고 생각한다.

구현

구현은 크게 4가지 포인트로 나눌 수 있을 것 같다.

Point1 - 모든 가능한 후보키들의 조합 만들기

Point1 - col 갯수에 따른 가능한 조합의 갯수

Ex)
col : 1 ------> 2^1 == 1 << 1 == 10(2진수) (1-1)
col : 2 ------> 2^2 == 1 << 2 == 100(2진수) (1-11)
col : 3 ------> 2^3 == 1 << 3 == 1000(2진수) (1-111)

int col = relation[0].length; // col의 갯수
int possibleCnt = 1 << col;       
for(int i = 1 ; i < possibleCnt ; i++) int keySet = i;

Point2 - 모든 가능한 후보키들의 조합 중에서 유일성을 만족하는 후보키들만 추출하기

Point2 - 선택한 Col들이 Uniqueness를 만족하는지 판단.

• Set을 활용하는 능력과
• Bit 연산자를 활용하여 1의 위치를 알아낼 수 있는 능력이 있어야 했다.

    /*
    	Point2 - 선택한 Col들이 Uniqueness를 만족하는지 판단.
     */
    boolean isUnique(int keySet, String[][] relation){
        int col = relation[0].length;
        List<Integer> list = new ArrayList<>();
        Set<String> set = new HashSet<>();
        // keySet중에서 1의 index를 찾는 과정.
        // 만약, 0110이면 list에는 [1,2]가 담긴다. -> 가장 오른쪽이 index 0이다.
        for(int i  = 0 ; i < col; i++){
            if(((keySet >> i) & 1) == 1) list.add(i);
        }
        // tuple중에서 list에 있는 index만을 이용해서 하나의 String을 만들고
        // 해당 String을 이용해서 중복을 검사한다.
        for (String[] tuple : relation) {
            StringBuilder str = new StringBuilder("");
            for (Integer idx : list) {
                str.append(tuple[idx]);
            }
            if(!set.add(str.toString())) return false;
            // 새로 만든 문자열이 set에 들어가지 않으면 이미 똑같은게 있다는 의미이기 때문에 early return 한다.
        }
        return true;
    }

Point3 - 후보키들의 조합을 정렬하기

Point3 - 선택한 것들을 내가 원하는 기준으로 정렬 할 수 있는가?

이 문제에서는 2진수로 표현했을때 1의 갯수가 적은 순으로 integer 값을 정렬 할 수 있는 능력이 필요하다.
즉, Comparator를 평소에 원하는 입맛대로 사용 할 수 있는 능력이 있어야 한다.

        // 해당 keySet들을 1의 갯수를 적게 가진 순으로 정렬한다.
        Collections.sort(uniquenessOks, new Comparator<Integer>() {

            int getCntOf1(int n){
                int cnt = 0;
                while (n != 0){
                    if((n & 1) == 1)  cnt++;
                    n = n >> 1;
                }
                return cnt;
            }

            @Override
            public int compare(Integer o1, Integer o2) {
                 int cnt1 = getCntOf1(o1);
                 int cnt2 =  getCntOf1(o2);
                 return Integer.compare(cnt1, cnt2);
            }
        });

        return uniquenessOks;
    }

Point4 - 유일성을 만족하는 후보키들 중에서 최소성을 만족하는 후보키들 추출하기

순회하는 과정에서 값의 변동이 생기기 때문에 Iterator를 이용하는 것이 가장 좋다.

for loop을 이용해서 index로 순회 하는 방법은 순회 하는 과정에서 index가 바뀌기 때문에 적절하지 않다.

   public List<Integer> findMinimality(List<Integer> uniquenessOk){
        List<Integer> minimalityOk = new ArrayList<>();

        while(!uniquenessOk.isEmpty()){
            int cur = uniquenessOk.remove(0);
            minimalityOk.add(cur);
            Iterator<Integer> iterator = uniquenessOk.iterator();

            while (iterator.hasNext()){
                if((iterator.next() & cur) == cur) iterator.remove();
            }
        }

        return minimalityOk;
    }

헤맸던 부분

헤맨 부분들 정리

잘못된 접근 방법 : 처음엔 백트래킹으로 문제를 접근했다.

DFS를 사용하여 가능한 조합들을 모두 만들어 보면서 해당 조합이 유일성을 만족하면

해당 조합에 새로운 것이 추가되는 모든 경우를 배제 하기 위해서 Branching을 했다.

하지만, 문제 이해가 잘못 되었다.

(0,1,2,3) 4가지 컬럼이 있을 경우

만약 (1,2)가 유일성을 만족한다고 했을 경우 브랜칭을 해주게 되면
(1,2,3)
(1,2,3,4)
(1,2,4) 는 자동으로 제외된다.

하지만 이후에 (2)가 유일성을 만족하게 되면, (1,2)는 최소성을 만족하지 못하기 때문에 후보키로 사용 될 수 없다. 즉, 애초에 문제 접근 방식이 잘못 되었다.

올바른 접근 방법 :

1. 유일성을 만족하는 부분집합을 모두 찾고

2. 해당 부분집합을 원소의 크기 순으로 오름차순으로 정렬 한 뒤

3. 크기가 작은 부분집합부터 확인하면서 해당 부분집합을 부분집합으로 가지는 더 큰 부분집합들을 제거한다.

얻은 것

부분 집합의 표현 방식

DFS를 이용한 방법으로 모든 부분 집합을 구할 수 는 있지만, 그렇게 하려니 너무 복잡했다.

이럴때에는 2진법의 특성을 이용하여 부분집합을 표현 할 수 있는 방법을 이 문제를 통해서 알게 되었다.

이러한 표현 방식을 사용하게 되면, A라는 부분집합이 B라는 부분집합의 부분집합인지 비트 마스킹을 통해서 손쉽게 해결 할 수 있다는 사실도 알게 되었다.

{'A','B','C','D'}의 부분 집합중 하나인

{'C','D'}를 리스트로 표현했다면 해당 집합이 {'C','D','E'}라는 집합의 부분집합 인 것을 확인하기 우해서 2중 for loop을 사용해야 했을 것이다.

하지만,

A : {'C','D'} 를 3 --> (2진수 = 0011);
B : {'C','D','E'} 를 7 --> (2진수 = 0111);

나타 낸다면 A가 B의 부분집합인지 판단하기 위해서는

A == B & A 인지 확인 해주면 되기 때문에 상수 시간에 끝이 나게 된다.

앞으로 부분 집합을 표현 할 때에는 이렇게 비트로 부분집합을 표현 해보는 것도 고려해 보는 것이 좋을 것 같다.

전체 코드 [ 내 코드 ]

package programmers.level2.후보키;

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        String[][] relation = {
                {"100","ryan","music","2"},
                {"200","apeach","math","2"},
                {"300","tube","computer","3"},
                {"400","con","computer","4"},
                {"500","muzi","music","3"},
                {"600","apeach","music","2"}
        };
        Solution solution = new Solution();
        System.out.println(solution.solution(relation));
    }

    public int solution(String[][] relation) {
        int answer = 0;
        List<Integer> uniqueKeySet = findUniqueness(relation);
        List<Integer> answerList = findMinimality(uniqueKeySet);
        return answerList.size();

    }

    /*
    Point4 - Iterator를 이용하여 최소성을 만족하지 않는 key들 제거하기
     */
   public List<Integer> findMinimality(List<Integer> uniquenessOk){
        List<Integer> minimalityOk = new ArrayList<>();

        while(!uniquenessOk.isEmpty()){
            int cur = uniquenessOk.remove(0);
            minimalityOk.add(cur);
            Iterator<Integer> iterator = uniquenessOk.iterator();

            while (iterator.hasNext()){
                if((iterator.next() & cur) == cur) iterator.remove();
            }
        }

        return minimalityOk;
    }

    /*
    Point2 - 선택한 Col들이 Uniqueness를 만족하는지 판단.
     */
    boolean isUnique(int keySet, String[][] relation){
        int col = relation[0].length;

        List<Integer> list = new ArrayList<>();
        Set<String> set = new HashSet<>();

        for(int i  = 0 ; i < col; i++){
            if(((keySet >> i) & 1) == 1) list.add(i);
        }

        for (String[] tuple : relation) {
            StringBuilder str = new StringBuilder("");
            for (Integer idx : list) {
                str.append(tuple[idx]);
            }
            if(!set.add(str.toString())) return false;
        }

        return true;
    }

    List<Integer> findUniqueness(String[][] relation){
        ArrayList<Integer> uniquenessOks = new ArrayList<>();
        int col = relation[0].length; // col의 갯수
        int possibleCnt = 1 << col;

        /*
        Point 1 - col 갯수에 따른 가능한 조합의 갯수
        각각의 col을 key의 attribute로 포함할지, 포함하지 않을지를 고려 해야 하기 때문에

        Ex)
            col : 0 ------> 2^0 == 1 << 0 == 1(2진수)
            col : 1 ------> 2^1 == 1 << 1 == 10(2진수)
            col : 2 ------> 2^2 == 1 << 2 == 100(2진수)
            col : 3 ------> 2^3 == 1 << 3 == 1000(2진수)
         */
        for(int i = 1 ; i < possibleCnt ; i++){
            int keySet = i;
            if(isUnique(keySet, relation)) {
                uniquenessOks.add(keySet);
            }
        } // 유일성을 만족하는 것들을 찾아내고

        /*
        Point3 - 선택한 것들을 내가 원하는 기준으로 정렬 할 수 있는가?
        이 문제에서는 2진수로 표현했을때 1의 갯수가 적은 순으로 integer 값을 정렬 할 수 있는 능력이 필요하다.
        즉, Comparator를 평소에 원하는 입맛대로 사용 할 수 있는 능력이 있어야 한다.
         */
        // 해당 keySet들을 1의 갯수를 적게 가진 순으로 정렬한다.
        Collections.sort(uniquenessOks, new Comparator<Integer>() {

            int getCntOf1(int n){
                int cnt = 0;
                while (n != 0){
                    if((n & 1) == 1)  cnt++;
                    n = n >> 1;
                }
                return cnt;
            }

            @Override
            public int compare(Integer o1, Integer o2) {
                 int cnt1 = getCntOf1(o1);
                 int cnt2 =  getCntOf1(o2);
                 return Integer.compare(cnt1, cnt2);
            }
        });

        return uniquenessOks;
    }
}

느낀점

알고리즘적인 테크닉을 기르는 것도 중요하지만, 결국 가장 중요한 것은 문제를 정확하게 이해하는 것 같다.

참조

ezsw 님의 유튜브 영상

• 해당 링크에 가면 친절하고, 직관적으로 설명해 주신다.
• 해당 영상을 보면 문제를 정확하게 이해 할 수 있다.