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

문제 설명

후보키

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

그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(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개이다.

 

 

 

풀이

개인적으로 되게 어려웠습니다.

 

비트마스킹을 처음 접한게 약 반년 전인데,

https://suhyeokeee.tistory.com/114

https://suhyeokeee.tistory.com/115?category=837216

 

그 이후에 비트마스킹 관련된 문제를 풀 지 않으니 다 까먹었습니다.

 

다시 복기용으로, 비트마스킹에 대한 정리를 조금 해보려고 합니다.

 

아래 코드만 보고 이해가 되시는분은 굳이 아래의 설명을 보지 않으셔도 됩니다.

import java.util.*;
class Solution {
      public int solution(String[][] relation) {
        int answer =0;
        
        int row = relation.length;
        int col = relation[0].length;
        ArrayList<Integer>list = new ArrayList<>();
        for(int i=1; i<=(1<<col)-1; i++) {
            HashSet<String>set = new HashSet<>();
            for(int j=0; j<row; j++) {
                String str = "";
                for(int k=0; k<col; k++) {
                    if((i&(1<<k))>0) {
                        str+=relation[j][k];
                    }
                }
                set.add(str);
            }
            if(set.size()==row && isPossible(list,i)) {
                list.add(i);
            }
        }
        
        answer = list.size();
        return answer;
    }
    public static boolean isPossible(ArrayList<Integer>list, int idx) {
        for(int a : list) {
            if((a&idx)==a) {
                return false;
            }
        }
        return true;
    }
}

 

 

 

 

 

 

 

우선 가장 간단한 and연산과 or연산을 살펴보겠습니다.

각 비트끼리 and 그리고 or 연산을 진행하는 간단한 것입니다.

 

비트연산을 하기위해 우선 4와 3을 2진수로 표시해봅시다.

 

임의로 비트의 길이는 4라고 정했을때

4= 0100

3= 0011 입니다

 

xxxxxxxxxx
int a= 4;
int b = 3;
​
int and = (a&b);
int or = (a|b);
​
System.out.println(and);    // 결과 0
System.out.println(or); // 결과 7

 

연산을 한 값이 2진수가 아닌 10진수로 나옵니다

헷갈릴수도 있어 실제로 나온 값을 2진수로 찍어보겠습니다.

xxxxxxxxxx
int and = (a&b);
int or = (a|b);
​
System.out.println(Integer.toBinaryString(and));    // 결과 0
System.out.println(Integer.toBinaryString(or));     // 결과 111

 

즉 비트연산을 한 값은 10진수로 저장 되는 걸 알 수 있습니다.

 

 

다음은 쉬프트 연산입니다

1<<3 이라는 것이 무엇을 의미하냐면 1을 오른쪽으로(화살표방향) 3칸 민다는 것입니다.

xxxxxxxxxx
int a = 1<<3;
System.out.println(a);                          //결과 8
System.out.println(Integer.toBinaryString(a));  // 결과 1000

 

이번에도 마찬가지로 10진수로 8이 들어갔지만 이걸 다시 2진수로 찍어보면 1000이 나오는 걸 알 수 있습니다.

 

 

다음은 위에서 얻은 결과값 1000을 왼쪽으로 밀어보겠습니다.

int a = 1<<3;
int b = a>>2;
System.out.println(b);                          //결과 2                  
System.out.println(Integer.toBinaryString(b));  //결과 10

기존에 1000에서 왼쪽으로 2칸을 밀었으니 1000 중 3번째 0과 4번째 0은 밀려서 값이 없어지고

10 이라는 2진수 값을 얻을 수 있습니다.

이를 10진수로 표시하면 2입니다.

 

그 다음 ~ 연산도 있습니다.

이 연산은 1의 보수를 생각하시면 될 것 같습니다.

0이면 1로

1이면 0으로 바꿔줍니다.

 

예를들어 a = 1000 이면

~a 를 하면 0111 이 나오게 됩니다.

 

이것으로 기본적인 비트마스킹을 위한 비트 연산에 대한 설명을 끝내고 문제에 대한 설명을 하겠습니다.

 

문제에서는 후보키를 찾는 내용이였습니다.

 

이 문제의 예시에 있는 후보키는 학번 + (이름+전공) 입니다.

그러면 이를 어떻게 프로그래밍 적으로 구현을 할까요?

 

학번, 이름, 전공, 학년 순으로 후보키를 구하려면 (최소성은 뒤에 다룹니다) 유일성만 고려하면

 

1. 학번으로 후보키를 이룰수 있는지 체크
2. 이름으로 후보키를 이룰수 있는지 체크
3. 전공으로 후보키를 이룰수 있는지 체크
4. 학년으로 후보키를 이룰수 있는지 체크

 

만약 위의 4개의 과정을 거치고도 만들수 없다면 어떻게 할까요?

학번+이름

학번+전공

학번+학년

 

이름+전공

이름+학년

 

전공+학년

 

이렇게 2개의 항목을 써서 후보키를 만들수 있는지 체크를 해줍니다.

 

만약 2개로도 못만든다면 어떻게 해야 할까요?

3개의 항목을 써서 후보키를 만들수 있는지 체크를 해줘야 합니다.

 

이를 자세히 보시면 이는 조합과 일치하는 걸 알 수 있습니다

 

이를 위해서 비트마스킹으로 이 문제를 풀이해보겠습니다.

비트마스킹에서 2진수는 0과 1로 이루어져있고 1은 선택 0은 선택하지 않은 것 이라고 생각하시면 됩니다.

학번 이름 전공 학년이 있을때 비트들의 상태를 아래처럼 두면 됩니다.

0001 = 학년만 선택

0010 = 전공만 선택

0100 = 이름만 선택

1000 = 학번만 선택

 

감이 오시나요?

그렇다면 1001 일땐 어떤 항목을 선택한 것일까요?

1의 위치와 (학번 이름 전공 학년)의 위치를 비교해보면

학번 + 학년을 선택 한 것이라고 할 수 있습니다.

 

그러면 아까 위에서 쉬프트 연산을 했던 것 처럼

(1<<n)-1 을 하면 됩니다.

 

더 자세하게 설명을 드리면 n=3인 [a,b,c] 배열의 조합을 뽑는다 가정하면 7가지가 나옵니다

a

b

c

ab

bc

abc

 

아무것도 안뽑는 조합을 제외하면 7가지가 나오게 됩니다.

아까 위에서 다뤘던 쉬프트 연산 1<<3을 하면 8이 나왔죠?

7가지를 사용하니까 (1<<3)-1을 하는 것 입니다.

 

xxxxxxxxxx
for(int i=1; i<=(1<<3)-1; i++) {
    System.out.println(i);
}
​
/* 출력결과      2진수로 표현하면
1                  001
2                  010
3                  011
4                  100
5                  101
6                  110
7                  111
*/

 

이렇게 아까 위에서 설명했던 것 처럼 비트마스킹의 2진수를 표현한 (1은 선택 0은 선택하지 않음) 것을 활용 할 수 있습니다.

 

문제 풀이 전략을 이와 같이 세웁니다.

 

비트마스킹을 이용해서 모든 조합별로 후보키를 이룰수있는지 체크하고 다 만든 다음에 최소성을 고려하자 !

 

먼저 후보키를 이룰수있는 것들을 구하는 로직입니다.

x
public int solution(String[][] relation) {
    int answer =0;
​
    int row = relation.length;
    int col = relation[0].length;
    ArrayList<Integer>list = new ArrayList<>();
    for(int i=1; i<=(1<<col)-1; i++) {
        HashSet<String>set = new HashSet<>();
        for(int j=0; j<row; j++) {
            String str = "";
            for(int k=0; k<col; k++) {
                if((i&(1<<k))>0) {
                    str+=relation[j][k];
                }
            }
            set.add(str);
        }
        if(set.size()==row && isPossible(list,i)) {
            list.add(i);
        }
    }
​
    answer = list.size();
    return answer;
}

 

 

첫번째 for문의 경우 위에서 설명한 모든 조합을 구하기 위한 반복문입니다.

2번째 반복문은 학번,이름, 전공,학년을 다루기 위한 반복문입니다.

3번째 반복문이 조금 어려운데요

for(int k=0; k<col; k++) {
    if((i&(1<<k))>0) {
    str+=relation[j][k];
    }
}

 

예를 들어봅시다. 첫번째 반복문에서 i가 7라고 칩시다. (2진수 0111)

그러면 이름,전공,학년 3가지를 선택했을때 후보키를 이룰수있냐 없느냐를 구하는 로직인데요

여기서 k는 학번,이름,전공,학년 까지 다 순회를 도는데 저희는 이름,전공,학년만 사용해서 후보키를 만들어야하니 학번을 빼야겠죠?

 

위의 예시에서는 학번을 제외해야 하니까 k가 3일때 예시를 들어보겠습니다

i = 7 이고 k가 3일때 and연산을 통해 (1<<k) 를 하면 1000 이 나오게 됩니다

 

2진수로 표시하면

i = 0111

k= 1000

 

이것을 and 연산하면 값이 0이 나옵니다. 즉 위에서 구한 조합에 해당하지 않는 것은 0이 나옵니다.

 

그렇다면 또 다른 예를들어서 학년을 선택했다고 해볼까요

그러면 i=7 k=0 이고

i = 0111

k = 0001

 

이걸 and 연산하면 지금 위의 조합에는 해당 비트를 포함하고 있기 때문에 0 이상이 나옵니다.

이것을 바탕으로 String에 저장해줍니다.

 

 

public int solution(String[][] relation) {
    int answer =0;
​
    int row = relation.length;
    int col = relation[0].length;
    ArrayList<Integer>list = new ArrayList<>();
    for(int i=1; i<=(1<<col)-1; i++) {
        HashSet<String>set = new HashSet<>();
        for(int j=0; j<row; j++) {
            String str = "";
            for(int k=0; k<col; k++) {
                if((i&(1<<k))>0) {
                    str+=relation[j][k];
                }
            }
            set.add(str);
        }
        if(set.size()==row && isPossible(list,i)) {
            list.add(i);
        }
    }
​
    answer = list.size();
    return answer;
}

그러면 set에다가 문자열을 넣어주게 되는데 set은 중복된 원소를 add해도 넣어주지 않습니다.

set.size()==row의 개수랑 같아야 유일성을 만족합니다

set.size!=row 라는 것은 중복된 데이터가 있어서 set에 들어가지 않았다는 것입니다.

 

예를들어서

학년

1

2

3

3

 

이렇게 있을때 set의 사이즈는 3이되므로 유일성이 만족되지 않습니다.

 

그다음 최소성을 구해보겠습니다.

 

xxxxxxxxxx
// import java.util.*;
// class Solution {
//       public int solution(String[][] relation) {
//      int answer =0;
        
//      int row = relation.length;
//      int col = relation[0].length;
//      ArrayList<Integer>list = new ArrayList<>();
//      for(int i=1; i<=(1<<col)-1; i++) {
//          HashSet<String>set = new HashSet<>();
//          for(int j=0; j<row; j++) {
//              String str = "";
//              for(int k=0; k<col; k++) {
//                  if((i&(1<<k))>0) {
//                      str+=relation[j][k];
//                  }
//              }
//                 set.add(str);
//          }
            if(set.size()==row && isPossible(list,i)) {
                list.add(i);
            }
        }
        
        answer = list.size();
        return answer;
    }
    public static boolean isPossible(ArrayList<Integer>list, int idx) {
        for(int a : list) {
            if((a&idx)==a) {
                return false;
            }
        }
        return true;
    }
}

 

주석된 부분을 제외하는 부분이 최소성을 구하는 로직입니다.

 

예를들어 학번,이름으로 후보키를 만들수 있다면 학번,이름,학년은 최소성에 위배됩니다.

굳이 학년이 없어도 학번+이름으로 후보키를 만들수 있기 때문이죠

 

list에 들어가는 것은 최소성과 유일성을 만족하는 후보키 입니다

int형으로 들어가지만 숫자 3이 들어간다면 (0011) 학년과 전공을 선택한 조합이 후보키가 된다가 되겠죠

 

예를들어 리스트에 0011이 들어있고 유일성을 만족한 조합이(0111) 들어왔다고 치면 최소성을 검사해야합니다.

그래서 a&idx == a 를 하면 구분 할 수 있습니다.

 

0011 과 0111을 and 연산하면

0011

0111

 

0011로 자기 자신 값이 그대로 나오는 것을 알 수 있습니다.

 

어 그러면 0111 과 0011을 and하면

 

0011이 나와서 0111과 다른데요? 라고 생각 하실수도 있는데 (사실 제가 했었습니다 ㅋㅋ)

반복문에서는 i가

0001

0010

0011

0100 --A

0101 --B

이런식으로 진행이 되니 걱정 하실 필요가 없습니다.

A와 B를보면 A는 2번째항목이 선택 , B는 2번째 4번째 항목이 선택됐네요

 

반복문의 순서상 더 적은 선택을 하는게 먼저 리스트에 들어가서 그런 걱정은 안하셔도 됩니다.