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

프로그래머스

---

코드

 

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

public class Solution {

    ArrayList<Integer> cKeyList;
    int n, m;

    public int solution(String[][] relation) {

        cKeyList = new ArrayList<>();   // 후보키 리스트
        m = relation[0].length;         // m개의 컬럼
        n = relation.length;            // n개의 데이터

        // 완전 탐색
        for(int i = 1; i < (1<<m); i++) {
            Set<String> checkUnique = new HashSet<>();
            // n개의 데이터
            for (int j = 0; j < n; j++) {
                StringBuilder sb = new StringBuilder();
                // m개의 컬럼
                for (int k = 0; k < m; k++) {
                    // 모든 경우의 수 & 해당 컬럼 조합 : 부분 집합 선택
                    if ((i & (1 << k)) > 0)
                        sb.append(relation[j][k]);
                }
                checkUnique.add(sb.toString());
            }
            // 유일성 확인
            if (checkUnique.size() != n) continue;
            // 최소성 확인
            checkMin(i);
        }
        return cKeyList.size();
    }
    public void checkMin(int i) {
        for (Integer cKey : cKeyList)
            if ((cKey & i) == cKey) return;
        cKeyList.add(i);
    }
}

 

내용

   
     문제를 풀긴 했지만 복잡하여 비효율적인 코드로 풀어 다른 사람의 풀이를 찾아보았다.

     주로 BFS, DFS로 풀거나 비트 마스킹 두 가지가 많이 활용되었다.

     특히 비트 마스킹이 효율적으로 보여, 풀이를 정리해보았다.

 

비트 마스킹

 

• 강점 : 비트를 활용하므로 연산이 빠르다.
• 활용 : 부분 집합 처리에서 특히 활용적일 것으로 보인다.
  
  for ( int i = 0; i < (1<<m); i++ ) 으로 속성 칼럼의 부분 집합을 전부 순회할 수 있다.
  
  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
  
  해당 숫자는 다음을 의미한다.
  
  

  

  
  
  그 다음 & 연산을 이용하여 부분 집합을 선택한다.
  해당 과정을 출력하면 다음과 같다.
  
  

 

유일성 확인 : Set

 

• set 은 중복성을 지니지 않는다.
  각 튜플의 값들을 set으로 옮겨 중복 데이터를 제거한다.
  
  

  

  
  이렇게 옮긴 후 기존 데이터 갯수와 set 데이터 갯수를 비교한다.
  같지 않을 경우 중복된 것임으로 유일성을 위반하여 이 경우 continue로 다음 반복을 진행한다.
  
  

최소성 확인

 

• & 연산 사용
  최소성 또한 비트 마스킹으로 & 연산을 사용하여 확인할 수 있다.
  
  2 (0010) 의 경우 6 (0110) 의 부분 집합이다.
  연산을 진행해보면
  
  2 & 6 => 0010 & 0110 => 0010
  
  으로 부분 집합인 집합이 결과로 도출된다.
  
  이런 방식으로 후보키 리스트의 집합들과 비교하여 후보키 리스트 안의 집합이
  결과로 도출되는 경우 최소성이 위반됨을 확인할 수 있다.
  위반하지 않는 경우, 해당 집합을 후보키 리스트에 추가한다.