[프로그래머스] 후보키 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

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

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

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

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

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

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

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

2. 입력

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

3. 예제

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

4. 풀이

문제를 풀기위해서는 유일성과 최소성을 맞추는 일이 주 작업이 될 것입니다.

 

• 최소성
  최소성을 확인하기 위해서는 Column의 조합 중 현재 조합의 칼럼 개수보다 작은 칼럼의 개수 조합이 포함되어 있으면 해당 컬럼의 조합은 최소성에 만족하지 않으므로 후보 키가 될 수 없습니다.
  
  0번 Index의 칼럼이 유일한 경우 0이 포함된 조합은 후보 키가 될 수 없고 1, 2번 Index의 컬림이 유일 한 경우는 1과 2가 포함된 조합은 후보키가 될 수 없습니다.
  
  

  for (String sub : indexList) {
  	int count = 0;
  	for (int i = 0; i < sub.split("").length; i++) {
  		if(result.toString().contains(String.valueOf(sub.charAt(i))))
  			count++;
  	}
  
  	if (sub.length() == count)
  		return;
  }​

  위 코드를 통해 Combination 함수에서 현재 만들어진 조합 문자열과 이전 후보 키로 선정된 List(indexList)를 순회하면서 비교합니다.
  
  이전 후보 키 문자열의 문자가 현재 조합 문자열에 포함되어 있는 개수를 확인 만약 이전 후보키 길이와 현재 조합 문자열에서 포함된 문자의 개수가 같으면 해당 조합은 최소성을 만족하지 않으므로 후보 키에서 탈락하게 됩니다.
• 유일성
  Combination 함수에서 최소성 검사를 통과한 조합 문자열에 한하여 유일성 검사를 진행 합니다.
  
  최소성에 통과를 하지 못한 조합의 경우는 해당 조합이 유일 하더라도 이미 최소성에서 탈락하여 후보키가 될 수 없기 때문 입니다.
  
  유일성 확인은 조합으로 만들어진 Index 문자열의 Column의 값을 하나의 문자열로 합친 후 Set에 해당 문자열이 있는지 확인하여 만약 해당 문자열이 있다는 것은 해당 조합은 유일 하지 않다는 것으로 후보키에서 탈락하게 됩니다.
  
  

  Set<String> set = new HashSet<>();
  
  for (String[] strings : relation) {
  	StringBuilder builder = new StringBuilder();
  	for (int j = 0; j < index.split("").length; j++) {
  		builder.append(strings[Integer.parseInt(String.valueOf(index.charAt(j)))]);
  		builder.append("/");
  	}
  
  	if (set.contains(builder.toString()))
  		return false;
  	else
  		set.add(builder.toString());
  }
  
  return true;​

  위 코드를 통하여 조합으로 만들어진 문자열의 Index에 해당하는 Column의 값을 하나의 문자열로 만들어 해당 문자열이 Set에 있는지 확인 만약 Set에 문자열이 있다면 중복 되는 것으로 유일성을 만족하지 않는 것으로 후보키에서 탈락 하게 됩니다.
  
  Column의 값들을 하나의 문자로 만들 때 "/" 구분자를 두는 경우는 하나의 문자열로 만들 경우 다른 문자이지만 같은 문자처럼 만들어 지는 경우가 발생하게 되어 구분자를 추가하여 구분하게 되었습니다.
  
  예를 들어 김가방이라는 문자열은 김, 가방 두 글자가 하나로 합쳐저 김가방이 되고 김가, 방 두 글자가 하나로 합쳐저서도 가능 합니다.
  
  이러한 문제를 방지하기 위해 구분자를 이용 하였습니다.
  
  
• 후보키 List 추가
  Combination 함수에서 최소성과 유일성을 모두 통과한 후보키는 List에 담아 후보키를 보관한 뒤 만들 수 있는 조합의 최소성, 유일성 확인 끝나면 해당 List의 길이가 가능한 후보키의 숫자가 되므로 Size를 return 합니다.

 

5. 코드

전체 코드는 Git에 있습니다.

private String[][] relation;
private final List<String> indexList = new LinkedList<>();

public int solution(String[][] relation) {
	this.relation = relation;

	String[] arr = new String[relation[0].length];
	for(int i=0; i<relation[0].length; i++)
		arr[i] = Integer.toString(i);

	for (int i = 1; i <= relation[0].length; i++)
		combination(arr, new boolean[relation[0].length], 0, i);

	return indexList.size();
}

public void combination(String[] arr, boolean[] check, int index, int r) {
	if (r == 0) {
		StringBuilder result = new StringBuilder();
		for (int i = 0; i < arr.length; i++) {
			if (check[i])
				result.append(arr[i]);
		}

		for (String sub : indexList) {
			int count = 0;
			for (int i = 0; i < sub.split("").length; i++) {
				if(result.toString().contains(String.valueOf(sub.charAt(i))))
					count++;
			}

			if (sub.length() == count)
				return;
		}

		if (dupleCheck(result.toString()))
			indexList.add(result.toString());
	} else {
		for (int i = index; i < arr.length; i++) {
			check[i] = true;
			combination(arr, check, i + 1, r - 1);
			check[i] = false;
		}
	}
}

public boolean dupleCheck(String index) {
	Set<String> set = new HashSet<>();

	for (String[] strings : relation) {
		StringBuilder builder = new StringBuilder();
		for (int j = 0; j < index.split("").length; j++) {
			builder.append(strings[Integer.parseInt(String.valueOf(index.charAt(j)))]);
			builder.append("/");
		}

		if (set.contains(builder.toString()))
			return false;
		else
			set.add(builder.toString());
	}

	return true;
}