구현

프로그래머스 2019 KAKAO BLIND RECRUITMENT Level 2 문제 후보키를 Java를 이용해 풀어보았다. 결국 못 풀었다. 완전 탐색 문제는 로직 자체는 간단한데 코드로 옮기는 게 참 어렵다...

문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/42890

---

유일성 조건 만족

후보키가 되기 위해서는 다음 두 조건을 만족해야 한다.
1. 유일성
2. 최소성

이 중 먼저 1번 조건을 만족시키는 목록을 만든다. 이 후에 최소성을 만족시키는 녀석들만 남겨두면 된다.

그럼 우선 모든 속성들의 가능한 모든 조합들을 만들며 중복이 있는지 체크해보면 된다. 모든 조합들을 어떤 방식으로 체크하냐면 비트를 이용해서 체크한다.

총 4개의 속성이 있다면 모든 조합을 다음과 같이 2진수로 표현할 수 있다.

0. 0000
1. 0001
2. 0010
   ...
3. 1111

공집합부터 모든 4개의 속성이 다 사용된 경우까지 위와 같이 비트값으로 커버할 수 있다. 그래서 위의 경우에는 16가지 경우에 대해 1인 자리만 확인해서 해당 속성들이 서로 다른 학생끼리 겹칠 경우는 유일성 키 목록에 추가하지 않고, 겹치지 않을 경우에는 유일성 키 목록에 추가해주면 된다. 이를 코드로 표현하면 다음과 같다.

for (int i = 1; i < (1 << atrNum); i++) 
       if (check(relation, i)) candidates.add(i);
            
static Boolean check(String[][] relation, int subsetBit) {
        for (int i = 0; i < stuNum - 1; i++) {
            for (int j = i+1; j < stuNum; j++) {
                boolean isSame = true;
                for (int k = 0; k < atrNum; k++) {
                    if ((subsetBit & (1 << k)) != 0) {
                        if (!relation[i][k].equals(relation[j][k])) {
                            isSame = false;
                            break;
                        }
                    }
                }
                if (isSame) return false;
            }
        }
        return true;
    }     

가능한 모든 학생의 조합들을 살펴보며 겹치는 속성이 있으면 false를 반환하고, 끝까지 다 뚫고 왔으면 true를 반환하면 된다.

---

최소성 조건 만족

위에서 candidates 리스트에 추가된 녀석들은 아직 최소성 조건을 통과하진 않은 녀석들이다. 최소성 조건을 확인해주기 위해 우선 특정 조건에 따라 정렬해줄 필요가 있다.

적은 수의 속성들만 포함된 녀석들을 앞으로 보내줘야 한다. 이렇게 정렬하게 되면 최소성을 이미 만족하는 녀석들이 앞쪽으로 오게 되기 때문이다.
이를 코드로 표현하면 다음과 같다.

Collections.sort(candidates,comp);

static Comparator<Integer> comp = new Comparator<Integer>() {
        Integer countBits(int n) { // 몇 개의 비트가 켜져있는지
            int res = 0;
            while (n != 0) {
                if ((n & 1) != 0) res++;
                n = n >> 1;
            }
            return res;
        }

        @Override
        public int compare(Integer o1, Integer o2) { // 더 적은 수의 비트가 켜져있는 애들이 앞으로 오도록
            int a = countBits(o1);
            int b = countBits(o2);

            if (a > b) return 1;
            else if (a < b) return -1;
            else return 0;
        }
    };

위와 같이 정렬을 마친 후에 맨 앞에 있는 녀석과 그 뒤에 있는 애들이 서로 겹치는 비트를 갖고 있는지를 확인해줘야 한다.

이때도 비트값을 & 연산을 통해 비교해서 맨 앞 녀석값이 가진 비트를 이미 다 갖고있으면 최소성을 만족 못하는 녀석이기 때문에 날려주면 된다. 이를 코드로 표현하면 다음과 같다.

while (candidates.size() != 0) {
            int n = candidates.remove(0);
            answer++;

            Iterator<Integer> itr = candidates.iterator();
            while (itr.hasNext()) {
                int cur = itr.next();
                if ((n & cur) == n) itr.remove();
            }
        }

이렇게 모든 작업을 마쳤으면 answer 값을 반환하면 된다.

다음은 내가 제출한 전체 코드다.

import java.io.*;
import java.util.*;

public class CandidateKey {
    static int stuNum, atrNum;

    static int solution(String[][] relation) {
        int answer = 0;
        stuNum = relation.length;
        atrNum = relation[0].length;
        List<Integer> candidates = new LinkedList<>();

        for (int i = 1; i < (1 << atrNum); i++)
            if (check(relation, i)) candidates.add(i);

        Collections.sort(candidates,comp);
        while (candidates.size() != 0) {
            int n = candidates.remove(0);
            answer++;

            Iterator<Integer> itr = candidates.iterator();
            while (itr.hasNext()) {
                int cur = itr.next();
                if ((n & cur) == n) itr.remove();
            }
        }

        return answer;
    }

    static Boolean check(String[][] relation, int subsetBit) {
        for (int i = 0; i < stuNum - 1; i++) {
            for (int j = i+1; j < stuNum; j++) {
                boolean isSame = true;
                for (int k = 0; k < atrNum; k++) {
                    if ((subsetBit & (1 << k)) != 0) {
                        if (!relation[i][k].equals(relation[j][k])) {
                            isSame = false;
                            break;
                        }
                    }
                }
                if (isSame) return false;
            }
        }
        return true;
    }

    static Comparator<Integer> comp = new Comparator<Integer>() {
        Integer countBits(int n) {
            int res = 0;
            while (n != 0) {
                if ((n & 1) != 0) res++;
                n = n >> 1;
            }
            return res;
        }

        @Override
        public int compare(Integer o1, Integer o2) {
            int a = countBits(o1);
            int b = countBits(o2);

            if (a > b) return 1;
            else if (a < b) return -1;
            else return 0;
        }
    };

    public static void main(String args[]) throws IOException {
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        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"}};
        int result = solution(relation);
        bfw.write(result + "");
        bfw.close();
    }
}

---

이 풀이는 다음의 영상을 참고(?베낌)해서 작성한 코드다.

오늘 배운 것

1. 비트 연산을 통한 풀이가 레벨이 올라갈수록 많이 나온다. 잘 배워두자.
2. 완전 탐색.. ㅆ...