[프로그래머스] 후보키 / 2019 KAKAO BLIND RECRUITMENT - JAVA

🔗 문제 링크

[프로그래머스] 후보키 / 2019 KAKAO BLIND RECRUITMENT

코딩테스트 연습 - 후보키

 

📝 풀이 과정

후보키에서 유일성과 최소성을 만족하는 키를 모두 구해야한다. 따라서 키의 모든 조합을 구해 모든 튜플을 식별할 수 있으면서 최소성을 만족하는지 확인하도록 했다.

 

조합을 구하는 방법 중 순차적으로 최소성을 만족하는 키가 먼저 등장하기 때문에 비트연산을 활용하는 방법을 사용하였다.

// 예시
0001
0010
0011
0100
...

 

 

// 기존 키 = k = 0011
// 조사할 키 = i = 1011

k & i == 0011 & 1011 == 0011

boolean ckMinimality(int i) {
  for (int k : key)
    if ((k & i) == k) return false;
  return true;
}

비트 연산을 활용한 조합을 돌리면서 해당하는 키가 먼저 최소성을 만족하는지 확인해주었다. 후보키의 리스트를 순차적으로 돌면서 현재 조사하는 키와 기존에 있는 키를 and연산을 했을 때 조사하는 키의 비트가 기존 키에 모두 포함된다면 기존 키의 값이 그대로 나오게 되므로 false를 반환해주었다.

 

 

만약 최소성을 만족했다면 비트가 1인 key로 이루어진 튜플의 속성을 모두 append해 Set에 넣어주었다. 만약 유일성을 만족하지 않는다면 Set이 자동으로 중복 처리해주기때문에 set.add()가 false가 나온다면 이미 있던 값이 추가로 들어갔기 때문에 break로 반복문을 나와주었다.
set의 크기가 튜플의 사이즈와 동일하다면 유일성과 최소성을 모두 만족시켰기 때문에 key List에 추가해주었다.

 

 

💻 코드

import java.util.*;

class Solution {
    List<Integer> key = new ArrayList<>();

    boolean ckMinimality(int i) {
        for (int k : key)
            if ((k & i) == k) return false;
        return true;
    }

    public int solution(String[][] relation) {
        int n = relation.length, m = relation[0].length;

        for (int k = 1; k < (1 << m); k++) {
            if (!ckMinimality(k)) continue;

            Set<String> set = new HashSet<>();
            for (int i = 0; i < n; i++) {
                StringBuilder key = new StringBuilder();

                for (int j = 0; j < m; j++) {
                    if (((1 << j) & k) > 0) key.append(relation[i][j]).append('/');
                }

                if (!set.add(key.toString())) break;
            }
            if (set.size() == n) key.add(k);
        }
        return key.size();
    }
}