🎯문제
프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.
그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(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개이다.
✏️풀이
코드
import java.util.*;
class Solution {
static String[][] r;
static Set<String> set;
// dfs 탐색 메서드
public void dfs(int index, int depth, int max, boolean[] selected) {
// 깊이가 max값과 동일할 경우
if(depth == max) {
String cols = "";
// 선택된 값들을 저장
for(int i = 0; i < selected.length; i++) {
cols += selected[i] ? i : "";
}
// 해당 값이 후보키로 사용 가능한지 탐색
if(possible(cols, selected)) {
// 사용 가능하다면 set에 저장
set.add(cols);
}
return;
}
// 탐색의 범위를 벗어날 경우 return
if(index >= selected.length) {
return;
}
// 해당 위치를 선택
selected[index] = true;
// dfs 탐색 시작
dfs(index + 1, depth + 1, max, selected);
// 해당 위치를 선택하지 않음
selected[index] = false;
// dfs 탐색 시작
dfs(index + 1, depth, max, selected);
}
// 후보키로 사용 가능한지 탐색하는 메서드
public boolean possible(String cols, boolean[] selected) {
// set에 저장되어있는 값들과 비교
for(String s : set) {
boolean flag = true;
for(int i = 0; i < s.length(); i++) {
// 값이 포함되어있지 않다면
if(!cols.contains(s.charAt(i) + "")) {
// flag를 false로 바꿔줌
flag = false;
}
}
// 값이 모두 포함되어있다면
if(flag) {
// false를 return
return false;
}
}
Set<String> value = new HashSet<>();
int[] col = new int[cols.length()];
int index = 0;
// 확인할 col의 값만 저장
for(int i = 0; i < selected.length; i++) {
if(selected[i]) {
col[index++] = i;
}
}
String v = "";
// 값의 중복이 있는지 확인
for(int i = 0; i < r.length; i++) {
v = "";
for(int j = 0; j < col.length; j++) {
v += r[i][col[j]];
}
// 중복된 값이 있다면 false를 return
if(value.contains(v)) {
return false;
} else {
value.add(v);
}
}
return true;
}
public int solution(String[][] relation) {
r = relation;
set = new HashSet<>();
for(int i = 1; i <= relation[0].length; i++) {
boolean[] selected = new boolean[relation[0].length];
dfs(0, 0, i, selected);
}
return set.size();
}
}설명
dfs 탐색을 사용해서 진행하였다.
탐색이 용이하도록 String[][] r의 배열에 relation을 저장해준다. set은 후보키가 될 수 있는 값들을 저장하는 용도이다.
dfs 탐색 메서드는 int형 변수 index, depth, max와 boolean형 배열 selected를 매개변수로 가진다.
각각의 매개변수의 뜻은 다음과 같다.
- index는 selected 배열의 index. 하나씩 탐색을 진행해주기 위해서 사용
- depth는 count의 개념으로 선택된 값이 몇개인지 저장
- max는 count의 최댓값
- selected는 col의 개수 중 선택여부를 저장할 배열
depth와 max가 동일할 경우는 조건에 만족하는 최댓값에 도달했으므로 더이상 탐색할 필요가 없기 때문에 return을 해준다. 이때 선택된 값들을 cols라는 변수에 저장을 해서 해당 값이 후보키로 사용이 가능한지 탐색을 진행한 뒤 사용이 가능하다면 set에 저장하고 return 해준다.
index는 selected 배열의 index로 탐색을 진행하면서 index가 selected 배열의 길이보다 크거나 같을 경우 탐색의 범위를 벗어났기 때문에 바로 return을 해준다.
탐색은 selected 배열을 사용해서 해당 위치를 선택하는 경우와 선택하지 않는 경우로 나뉠 수 있다.
선택을 하는 경우에는 selected[index] = true를 사용해서 해당 위치를 선택하고 index + 1을 사용해 다음 값을 탐색할 수 있도록 한다. 이때 depth + 1도 해주어 한개가 선택되었음을 저장해준다.
선택을 하지 않는 경우에는 selected[index] = false를 사용해서 해당 위치를 선택하지 않음을 저장한다. 마찬가지로 index + 1을 사용해서 다음 값을 탐색할 수 있도록 하지만 depth는 그대로 유지해준다. 선택하지 않았기 때문에 depth의 크기를 올려주지 않는 것이다.
possible 메서드는 후보키로 사용이 가능한지 탐색하는 메서드로 cols과 selected 배열을 매개변수로 가진다.
cols는 후보키로 사용하려고 하는 값이고, selected는 선택된 위치가 저장된 배열이다.
후보키로 사용이 가능하기 위해서는 최소성과 유일성을 만족해야한다.
먼저 최소성을 만족하는지 확인하기 위해 set에 있는 모든 값들과 비교를 진행한다. set에 있는 값을 하나씩 가져와서 charAt 함수를 사용하여 하나하나가 후보키로 사용하려고 하는 cols에 포함이 되는지 확인한다.
예를 들어, cols에는 123이 저장이 되어있고 set에는 13이 저장되어있다고 할 때
반복문을 사용하여
- 1은 123에 포함이 되는가? => 예
- 3은 123에 포함이 되는가? => 예
이런 식으로 set에 저장된 값 중 하나라도 모든 요소가 cols에 포함이 될 경우 최소성을 만족하지 않기 때문에 false를 return해준다.
포함이 되는 경우가 없다면 다음은 유일성을 판단해준다. 판단이 용이하도록 col 배열에 확인하고 싶은 위치만 저장을 해준다. 위의 예시를 그대로 가져오면 총 5개의 col이 있다고 할 때 1, 2, 3만 col 배열에 저장을 해주는 것이다.
이후 Set을 하나 생성하여 relation의 있는 값들을 탐색해준다. 만약 중복된 값이 있다면 유일성을 만족하지 않으므로 false를 return하고 중복된 값이 없다면 Set에 값을 저장한다.
위의 두 메서드를 사용해서 탐색을 진행하고 모든 탐색이 끝난 뒤 set의 크기를 반환해주면 문제를 해결할 수 있다!
💡느낀 점
level2의 문제였는데도 난이도가 쉽지 않았다. 특히 후보키의 개념이 헷갈려서 코드를 작성할 때 많이 헤매게 되었다.. 코드를 짜고 문제를 해결했지만 제대로 설명할 자신이 없어서 다른 분들의 블로그를 참고하여 코드를 수정하고 블로그를 작성하다보니 코드에 대한 이해를 더 확실히 할 수 있었다. level2 문제들을 꾸준히 풀고 있지만 역시 난 아직 멀었구나라는 생각을 안겨준 문제였다..
링크
지금 풀고 있는 lv1과는 확실히 자료구조의 개념을 알아야 문제가 잘 풀리겠네요...! 잘봤습니당:)