[프로그래머스] 카카오 블라인드 리쿠르트 2019 - 후보키 (Java)

 

 

코딩테스트 연습 - 후보키

문제 설명

후보키

프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.

그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.

후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.

• 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
  • 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
  • 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.

위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 "학번"을 가지고 있다. 따라서 "학번"은 릴레이션의 후보 키가 될 수 있다.
그다음 "이름"에 대해서는 같은 이름("apeach")을 사용하는 학생이 있기 때문에, "이름"은 후보 키가 될 수 없다. 그러나, 만약 ["이름", "전공"]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다.
물론 ["이름", "전공", "학년"]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다.
따라서, 위의 학생 인적사항의 후보키는 "학번", ["이름", "전공"] 두 개가 된다.

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

 

제한사항

• relation은 2차원 문자열 배열이다.
• relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
• relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
• relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
• relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

입출력 예

relation	result
[["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]	2

입출력 예 설명

입출력 예 #1
문제에 주어진 릴레이션과 같으며, 후보 키는 2개이다.

---

풀이

(비트마스크라는 낯선 개념이 들어갔던 문제로 조금 더 머릿속에 박아두기 위해 나름 빡시게 정리해봤다.)

대놓고 후보키에 대한 문제인 덕분에 데이터베이스 관련 지식을 쌓아둔 것이 문제 이해를 하는데 큰 도움이 되었다.

문제에도 나와있지만 후보키의 조건에는 유일성과 최소성이 있다.

 

유일성은 1개 이상의 컬럼을 묶어서 만든 값들 간에 중복이 없는 것을 의미하고,

최소성은 1개 이상의 컬럼을 묶어서 만들었지만 유일성을 만족하기 위해서는 묶은 컬럼 중 어느 하나도 뺄 수 없는 경우를 의미한다. (예를 들어 3개의 컬럼을 묶었는데 그중 하나를 빼도 여전히 유일성을 만족한다면 3개를 묶어 만든 키는 최소성을 만족하지 못하는 것)

 

 

후보키가 될 수 있는지 판별해야하는 대상은 컬럼들의 모든 부분 집합이다.

예를 들어 컬럼이 n개라고 하면 다음과 같은 경우를 모두 고려해야 한다.

컬럼 1개로만 키를 만든 경우 -> 1번째 컬럼, 2번째 컬럼, ... n번째 컬럼

컬럼 2개로만 키를 만든 경우 -> 1-2번째 컬럼, 1-3번째 컬럼, ... (n-1)-n번째 컬럼

...

컬럼 n개로만 키를 만든 경우 -> 1-2-...-n번째 컬럼

 

결국, 2^n번 비교해야하는 셈이 된다.(부분집합의 갯수는 2^n개)

 

 

 

이제 구현에 대해서 이야기해보자. 큰 흐름은 다음과 같을 것이라고 본다.

 

1. 후보키가 될 수 있는지 판별하려는 컬럼들의 집합을 구한다. (2^n번)

2. 해당 컬럼 집합이 유일성을 만족하는지 확인한다. 만족하지 않으면 해당 집합은 후보키가 될 수 없다.

3. 해당 컬럼 집합이 최소성을 만족하는지 확인한다. 만족하지 않으면 해당 집합은 후보키가 될 수 없다.

4. 두 조건을 만족하는 집합을 후보키가 가능한 값으로 보고 후보키 리스트에 추가한다.

5. 후보키 리스트의 사이즈를 리턴한다.

 

1번에서 컬럼 집합을 구하기 위한 방법으로 처음에는 백트래킹, dfs등을 사용하여 조합(combination)을 찾아내려하였다. 하지만 코드가 점점 장황해지고 복잡해지는 어려움이 있었다. 방법을 찾아보니 비트마스킹을 이용하면 더 효율적으로 해결이 가능했다.

 

컬럼의 포함 여부를 비트를 통해서 표현하는 방식으로 n개의 비트만으로 2^n가지의 경우를 모두 표현하는 것이 가능했다.

예를 들어, 컬럼의 갯수가 4개이고 첫번째와 세번째 컬럼을 포함하는 집합은 1010으로 표현 가능하다. 마찬가지로 3번째, 4번째는 0011으로 표현이 가능하다.

 

비트마스크를 활용하기 위해서는 비트 및 쉬프트 연산에 대해 잘 알아둘 필요가 있었다. 해당 문제에서 사용한 것만 간단히 적어보면

1 << n    ->  1을 왼쪽으로 n만큼 쉬프트한 것으로 n이 4라면, 1 << 4는 1000이 된다. 이는 이진수이기 때문에 16과 같다. 즉, 1 << n == 2^n인 것이다. (2를 n번 곱한 것)

n >> i     ->  n을 오른쪽으로 i만큼 쉬프트한 것으로 n이 4, i이 1이라면 4 >> 1는 100이 된다. 10진수로 표현하면 8이 된다. (2를 n번 나눈 것)

(n >> i) & 1 -> &연산은 비교 하는 두 수를 이진수로 표현했을 때 같은 자리의 값이 둘 다 1인 경우에 1을 리턴하고, 그렇지 않은 경우는 0을 리턴한다. 오른쪽 쉬프트 연산과 & 연산을 함께 사용함은 n을 2진수로 표현하고 i번째 자리의 값을 확인하기 위함이다. 예를 들어 n = 10, i = 1인 경우 n을 2진수로 표현하면 1010이므로 1010 >> 1은 101이다. 그다음 101 & 001 연산이므로 결과값으로 001로 i번째 값이 1임을 알 수 있다. 

 

 

다시 문제로 돌아와서 2^n번의 조회를 하여 유일성과 최소성을 만족하는 solution의 로직을 다음과 같이 구현하였다. (1 << colSize)는 결국 2^colSize만큼 for문을 돌리겠다는 것과 같다.

복잡한 유일성과 최소성 로직은 각각 isUnique(), isMinimum()메소드로 분리하였다.

        for (int i = 0; i < (1 << colSize); i++) {
            if (!isUnique(i)) {
                continue;
            }

            if (!isMinimum(i)) {
                continue;
            }

            candidateSets.add(i);
        }

 

 

2번에 해당하는 isUnique()메소드는 다음과 같다.

    private boolean isUnique(int set) {
        String[] keys = makeKeys(set);

        Set<String> keySet = new HashSet<>();
        for (String key : keys) {
            if (keySet.contains(key)) {
                return false;
            }
            keySet.add(key);
        }

        return true;
    }

매개변수 set은 앞서 설명한 비트마스크로 포함시킬 컬럼을 체크한 값이다.

set이 5라면 0101로 두번째, 네번째 컬럼으로 키를 만드는 상황인 것이다.

키를 만드는 기능은 makeKeys() 메소드로 분리하였고, 만들어진 key 배열을 HashSet에 담는다.

Set 자료구조는 중복을 허용하지 않는다. 그렇기 때문에 key 배열에 담긴 원소들의 중복 값을 체크할 수 있다.

중복이 존재한다는 것은 유일성을 만족하지 못한다는 의미로 이러한 경우는 false를 리턴한다. 중복이 없었다면 true를 리턴한다.

 

 

키를 만드는 기능을 수행하는 makeKeys() 메소드는 다음과 같다.

    private String[] makeKeys(int set) {
        List<Integer> indexes = new ArrayList<>();
        for (int i = 0; i < colSize; i++) {
            if (((set >> i) & 1) == 1) {
                indexes.add(i);
            }
        }

        String[] keys = new String[rowSize];
        for (int i = 0; i < rowSize; i++) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int j = 0; j < indexes.size(); j++) {
                stringBuilder.append(database[i][indexes.get(j)]);
            }
            keys[i] = stringBuilder.toString();
        }

        return keys;
    }

앞서 설명한 (set >> i) & 1)을 통해 비트마스크에서 1을 값으로 가지고 있는 자리를 찾는다.

1이 들어간 자리는 해당 번째의 컬럼을 키 값을 만드는데 사용하겠다는 것으로 indexes라는 리스트에 담아준다.

이후 본격적으로 keys값을 만들어 낼 때 각 로우에 indexes에 있는 컬럼들을 조회하여 키를 만들어 낸다.

 

 

마지막으로 최소성 여부를 체크하는 isMinimum() 메소드를 살펴보자.

    private boolean isMinimum(int set) {
        for (int candidateSet : candidateSets) {
            if ((candidateSet & set) == candidateSet) {
                return false;
            }
        }

        return true;
    }

마찬가지로 매개변수 set은 비트마스크 값이다. candidateSets 리스트는 그동안 검증을 통해 최종 후보키로 가능한 비트마스크를 저장하는 리스트다. 0부터 2^n까지 작은 값부터 차례로 조회했기 때문에 당연히 candidateSets에는 현재 set보다는 작은 집합 크기를 가지고 있다.

최소성을 보장한다는 건 그동안의 set중에서 현재 set의 부분집합이 되지 않는다는 것을 말한다.

이는 & 연산으로 찾아낼 수 있는데 & 연산은 비교하는 두 수의 해당 자리가 모두 1일 때 1을 리턴한다. 즉, 두 값 중 어느 하나가 다른 하나의 부분집합이 된다면 &연산 값은 그 부분집합이 되는 값이 된다. (예: 1110 & 0110 == 0110)

따라서 이러한 경우는 최소성을 만족하지 못한다고 볼 수 있다.

 

 

코드

import java.util.*;

public class Solution {

    private String[][] database;
    private int rowSize;
    private int colSize;
    private List<Integer> candidateSets;

    public int solution(String[][] relation) {
        rowSize = relation.length;
        colSize = relation[0].length;
        database = relation;
        candidateSets = new ArrayList<>();

        for (int i = 0; i < (1 << colSize); i++) {
            if (!isUnique(i)) {
                continue;
            }

            if (!isMinimum(i)) {
                continue;
            }

            candidateSets.add(i);
        }

        return candidateSets.size();
    }

    private boolean isUnique(int set) {
        String[] keys = makeKeys(set);

        Set<String> keySet = new HashSet<>();
        for (String key : keys) {
            if (keySet.contains(key)) {
                return false;
            }
            keySet.add(key);
        }

        return true;
    }
    
    private String[] makeKeys(int set) {
        List<Integer> indexes = new ArrayList<>();
        for (int i = 0; i < colSize; i++) {
            if (((set >> i) & 1) == 1) {
                indexes.add(i);
            }
        }

        String[] keys = new String[rowSize];
        for (int i = 0; i < rowSize; i++) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int j = 0; j < indexes.size(); j++) {
                stringBuilder.append(database[i][indexes.get(j)]);
            }
            keys[i] = stringBuilder.toString();
        }

        return keys;
    }

    private boolean isMinimum(int set) {
        for (int candidateSet : candidateSets) {
            if ((candidateSet & set) == candidateSet) {
                return false;
            }
        }

        return true;
    }
}