2019 카카오 블라인드 코딩테스트 - 후보키 (feat. Java)

문제 정보는 아래 링크를 확인해주세요!

[후보키]

프로그래머스

 

문제 접근 방법

• 컬럼들로 만들 수 있는 조합을 만든다 (비트마스킹)
• 현재 비트마스킹 조합에 해당하는 컬럼 조합을 만들고 SET 자료구조에 담는다.
• 만든 컬럼 조합의 수가 로우의 수랑 매칭이 돼야 후보키의 조건을 만족하므로 이를 검사한다.
• 현재 만든 조합에 대한 비트마스킹이 결과 리스트에 있는 값들과 부분집합인지 검사하고(&연산),
• 부분집합이 아니라면, 결과 리스트에 추가한다.

 

비트마스킹이란?

• n개의 값을 가지고 만들 수 있는 조합을 비트 연산을 통해 문제에서 구하고자하는 값을 구하는 방법!
• 문제에서는 컬럼의 조합을 비트마스킹으로 구하는데, 조합 일치 검사를 위해 &연산을 한다.
• 예를들어 4개의 컬럼(학번,이름,전공,학년)에 대해서 조합을 만들려고 할 때,
• 비트마스킹으로 표현하면, 0000부터 0001, 0010 ~ , 1110, 1111 이런 방식으로 조합을 만들 수 있다.
• 위 문제로 예를 들면 0101이라고 할 때, 이는 이름과 학년에 대한 조합을 만든다는 의미이고,
• 로우와 컬럼에 대한 분기문을 돌면서 컬럼의 인덱스와 0101을 &연산하여
• 0보다 큰 컬럼(조합에 해당하는 컬럼)일 경우 조합을 만들 수 있다는 의미이다.
• 이렇게 만든 조합이 후보키가 될 수 있는지를 판단하기 위해서는
• 후보키는 유일해야하는 특징이 있기 때문에 만든 후보키 조합의 수와 로우의 수가 일치해야하며,
• 다른 후보키 집합의 부분집합이 되지 않아야한다.
• 부분집합을 확인하기 위해서는 이미 조합이 결정된 결과 리스트의 값들과 현재 조합을 &연산하여
• 그 값이 현재 결과 리스트 값과 일치하면 부분집합이므로 추가하지 않는 방법이다.
• 컬럼 조합은 1개부터 시작하기 때문에 상위 갯수의 조합에 대한 확인이 가능하다.(문제 예시 참고!)

[소스 코드]

 

package algorithm.programmers;

import java.util.*;

/*
 * 2019 카카오 블라인드
 * 후보키
 * */
public class Pro42890 {
    public int solution(String[][] relation) {
        int answer = 0;
        int m = relation.length;
        int n = relation[0].length;

        ArrayList<Integer> ans = new ArrayList<>();

        //컬럼으로 만들 수 있는 조합을 비트마스킹으로 표현
        for (int i = 1; i<=(1<<n)-1;i++) {

            Set<String> set = new HashSet<>();//중복된 값을 조사하기 위한 set

            for (int j = 0; j < m; j++) {//로우

                StringBuilder sb = new StringBuilder();//조합을 만들 문자열 객체

                for (int k = 0; k < n; k++) {//컬럼

                    if ((i&(1<<k)) > 0) {//&연산을 통해 i로 만들 수 있는 조합에 해당하는 컬럼이면 해당 컬럼의 값을 추가
                        sb.append(relation[j][k]);//조합을 추가
                    }
                }

                set.add(sb.toString());//합쳐진 조합을 set에 추가
            }

            //만들어진 조합의 사이즈가 m과 같아야 후보키 조건을 만족하고,
            //check()를 통해 기존에 등록된 조합과 부분 집합을 이루는 조합이 있는지를 검사
            if (set.size() == m && check(ans,i)) {
                ans.add(i);
            }
        }

        answer = ans.size();
        return answer;
    }

    //등록된 조합(ans)과 부분집합이 있는지를 검사
    private boolean check(ArrayList<Integer> ans, int now) {

        for (int i = 0; i < ans.size(); i++) {

            if ((ans.get(i)&now) == ans.get(i)) return false;
        }

        return true;
    }

}

 

 

[정확성 테스트]

 

 

PS. 해당 문제는 비트마스킹으로 풀면 쉽지만, 비트마스킹을 알아야한다는 전제조건이 있으므로 개인적으로 굉장히 어렵다고 생각한 문제다. 하지만, 개발자로서 기본적인 비트 연산에 대한 개념을 알고 있어야한다고 생각하므로 도전해볼만한 가치가 있는 문제라고 생각한다!