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

[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 후보키 : https://programmers.co.kr/learn/courses/30/lessons/42890#

코딩테스트 연습 - 후보키 | 프로그래머스

 

 

관계형 데이터베이스에서 후보 키의 최대 개수를 구하는 문제다.

후보 키를 만족하려면 아래의 두 조건을 만족해야 한다.

• 유일성(Uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
• 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

 

이 문제에서는 key들의 집합을 나타내기 위해 비트마스크를 사용했다.

위의 테이블에서 [학번]은 비트마스크로 0001, [이름, 전공]은 0110으로 나타낸다.

 

비트마스크로 모든 부분집합을 탐색하면서, 최소성과 유일성을 체크해준다.

최소성과 유일성을 모두 만족해 후보 키를 만족하면 ArrayList에 키를 담는다.

유일성을 비교할 때는 각 튜플의 비교 부분들을 StringBuilder에 모두 더한 뒤,

Set에 담아서 중복되는 튜블이 있으면 false를 반환하는 식으로 구현했다.

 

 

총 걸린 시간 : 1시간

난이도 : ★★★☆☆

 

코드

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

class Solution {
    public int solution(String[][] relation) {
        int rowSize = relation.length;
        int colSize = relation[0].length;
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 1; i < (1 << colSize); i++) {
            if (!checkMinimality(i, list)) continue; // 최소성을 만족하지 못하면 패스
            if (!checkUniqueness(i, relation, rowSize, colSize)) continue; // 유일성을 만족하지 못하면 패스

            list.add(i);
        }

        return list.size();
    }

    private boolean checkMinimality(int set, ArrayList<Integer> list) {
        for (int key : list) {
            if ((set & key) == key) return false; // 중복 되어 있으면 false
        }
        return true;
    }

    private boolean checkUniqueness(int set, String[][] relation, int rowSize, int colSize) {
        ArrayList<Integer> s = getSet(set, colSize);

        HashSet<String> hashSet = new HashSet<>();
        for (int i = 0; i < rowSize; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j : s) {
                sb.append(relation[i][j]).append(" ");
            }
            hashSet.add(sb.toString());
        }
        return hashSet.size() == rowSize;
    }

    private ArrayList<Integer> getSet(int set, int colSize) { // 0101 -> [0, 2]로 변환
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < colSize; i++) {
            if (((set >> i) & 1) == 1) result.add(i);
        }
        return result;
    }
}