[알고리즘]프로그래머스 후보키

이 문제는 데이터베이스의 후보키의 개념을 알고 있더라도 문제에 접근하는 방법을 찾기가 쉽지 않았다.

 

첫 번째 방법으로는 dfs 혹은 bfs 를 활용하여 전체 경우의 수를 모두 탐색하는 방법을 떠올렸다.

 

제한 사항에 따르면 컬럼과 로우의 길이가 각각 8, 20 이하이기 때문에 dfs bfs 를 사용하여 풀 수 있을 것 같았지만 모든 칼럼의 부분집합의 경우의 수를 탐색하는 알고리즘을 떠올릴 수 없어 다른 방법을 찾아보기로 했다.

 

두 번째 떠오른 방법은 비트마스킹을 사용한 방법이다.

 

for문을 사용하면 아래와 같은 방법을 통해서 해당 칼럼의 부분집합 전체를 순회할 수 있는 방법이었다.

0 = 0000    8 = 1000

1 = 0001    9 = 1001

2 = 0010   10 = 1010

3 = 0011   11 = 1011

4 = 0100   12 = 1100

5 = 0101   13 = 1101

6 = 0110   14 = 1110

7 = 0111   15 = 1111

 

이제 숫자에서 1이 표시된 칼럼에 해당하는 문자열들을 띄어 쓰기로 구분하고 append 한 후에 set에 집어넣는 행위를 로우의 숫자만큼 반복했을 때, set의 사이즈와 로우의 값이 같으면 해당 칼럼의 집합은 유일성을 확보하게 된다.

ex)

유일성 확보 x

    "100 김박사 음악"                                "100 김박사 음악"

    "200 김박사 수학"          set에 add          "200 김박사 수학"

    "300 이박사 과학"              =>              "300 이박사 과학"

    "400 최박사 체육"                                "400 최박사 체육"

    "100 김박사 음악"

              5                                                     4

 

유일성 확보 o

    "100 김박사 음악"                                "100 김박사 음악"

    "200 김박사 수학"          set에 add          "200 김박사 수학"

    "300 이박사 과학"              =>              "300 이박사 과학"

    "400 최박사 체육"                                "400 최박사 체육"

    "500 김박사 물리"                                "500 김박사 물리"

              5                                                     5

 

그 다음은 유일성을 확보 했다면 최소성을 판단해야한다.

 

최소성을 판단하는 것은 간단하다. 정답에 포함되는 숫자들이 있는 리스트전체를 순회하여 현재 해당하는 숫자와 비교하여 & 연산을 했을 때 정답의 리스트에 해당하는 숫자가 나온다면 유일성이 깨진다.

ex)        정답 리스트                  현재 순회 번호

                 6                                  7

                110                               111

                               6 & 7 = ?

                                  110

                                  111

                                --------

                                  110

유일성이 깨지지 않는다면 정답 리스트에 해당 숫자를 넣으면 되고 유일성이 깨진다면 continue 하여 이번 순회를 넘어간다.

 

그렇게 코드를 짠다면 다음과 같은 결과가 나온다.

 

package KaKao.k10;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

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


    public int solution(String[][] relation) {
        int n = relation.length;
        int m = relation[0].length;
        List<Integer> answer = new ArrayList<>();

        for (int i = 1; i < (1 << m); i++) {
            Set<String> duplicateCheck = new HashSet<>();
            for (String[] strings : relation) {
                StringBuilder builder = new StringBuilder();
                String binary = getBinary(i, m);
                for (int k = 0; k < binary.length(); k++) {
                    if (binary.charAt(k) == '1') {
                        builder.append(strings[k]).append(" ");
                    }
                }
                builder.deleteCharAt(builder.length() - 1);
                duplicateCheck.add(builder.toString());
            }
            if (!isMinimal(answer, i)) {
                continue;
            }
            if(duplicateCheck.size() == n){
                answer.add(i);
            }
        }
        return answer.size();
    }

    private boolean isMinimal(List<Integer> answer, int i) {
        for (Integer integer : answer) {
            if((integer & i) == integer)
                return false;
        }
        return true;
    }

    public String getBinary(int number,int length) {
        String result = Integer.toBinaryString(number);
        int addCnt = length - result.length();
        return "0".repeat(Math.max(0, addCnt)) + result;
    }
}

level2에 왜 있는지 모를 어려운 문제였다고 생각한다.