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

문제

programmers.co.kr/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키

1. 모든 후보키 조합 구하기

조합을 구하는 알고리즘을 이용해 모든 후보키가 될 수 있는 조합을 구했다. (백트래킹 이용해 구현함)

 

조합 포스팅

[Java] 조합 Combination

 

구해진 후보키 조합은 문자열 형태로 구해진다.

예를 들어 4개의 애트리뷰트를 가진 릴레이션의 경우 0, 1, 2, 3, 01, 02, 03,... 023, 123, 0123 형태로 뽑아짐 

2. 후보키 유일성 판별

먼저 후보키 유일성을 판별한다.

조합으로 추출된 모든 후보키를 대상으로, 각 후보키가 가진 애트리뷰트 부분의 튜플만 뽑아낸다.

 

후보키는 012와 같이 String 형태이기에 split 메서드를 이용해 공백을 기준으로 잘라 String 배열을 만들어 주었다.

그리고 String 배열에 저장된 애트리뷰트에 해당하는 튜플의 값을 가져와 String 문자열로 만들어준다.

예를 들어 01의 경우 [100, ryan, music, 2] 튜플에서 [100, ryan]만 뽑아 String r = "100 ryan"으로 만들어지는 것.

 

만들어진 문자열을 HashSet에 저장해 중복을 없애준다.

각 후보키에 해당하는 모든 튜플을 뽑았다면 HashSet의 사이즈와 전체 튜플의 수를 비교한다.

만약 둘의 값이 같다면 모든 튜플을 유일하게 식별한 것임으로 다음 단계인 최소성 판별로 넘어간다.

3. 후보키 최소성 판별 

처음엔 String이기에 단순히 contains 메서드를 사용해 다른 후보키에 포함되지 않는 후보키만 뽑아낼려했다.

(후보키 길이가 짧은 순서로 진행되기에 포함만 안되면 가능하다고 생각ㅠ)

하지만 후보키 123, 13의 경우 contains 메서드 결과 false가 나와 원하는 결과를 얻을 수 없다.

순서가 다르더라도 포함된다면 후보키 최소성을 만족할 수 없다.

 

그렇기에 containsAll 메서드를 사용했다.

containsAll 메서드는 Collection에서 사용할 수 있는 메서드라서 후보키를 String에서 List로 바꿔주어야 했다.

Arrays.asList를 사용해 쉽게 List로 바꿔주었다. (Arrays.asList의 반환 값 ArrayList 안됨, List 여야함)

 

그리고 후보키를 저장하고 있는 candidateKeys의 모든 후보키를 앞에서 유일성을 검증한 key와의 포함 여부를 판단한다.

candidateKeys를 for문을 통해 다 돌며 어떠한 부분집합으로도 포함되는 것이 없다면

최소성 역시 부합하는 후보키가 된다.

 

유일성과 최소성 판별을 모두 통과한 후보키만을 담고 있는 candidateKeys의 size가 바로 정답이 된다.

여담

나는 엄청 복잡스럽게 푼 거 같다ㅠ_ㅠ

만약 애트리뷰트수가 커진다면 내 코드론 어림도 없을듯....

다 풀고 다른 사람의 풀이 봤는데 진짜 완전 깔끔하고 짧게 끝낸 사람 코드 많았음...대박적ㄱ

대충봐선가 이해가 안갔다ㅎㅎ

막 쉬프트 연산을 써서 쉽게 하는 거 같은데,,,담에 공부해봐야겠다~!

전체 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

class Solution {	
   	public static ArrayList<String> list = new ArrayList<>(); // 모든 후보키 조합 저장 
	public static ArrayList<List<String>> candidateKeys = new ArrayList<>(); // 유일성, 최소성 만족하는 후보키 저장 
           
    public int solution(String[][] relation) {
		int tuple = relation.length;
		int column = relation[0].length;
		boolean[] visited = new boolean[column];
	
		for(int i = 1; i <= column; i++) { // 조합을 이용해 모든 후보키 조합 추출 
			comb(visited, 0, i);
		}

		// 후보키 유일성 판별
		for(int i = 0; i < list.size(); i++) {  
			HashSet<String> set = new HashSet<>(); // 중복 없이 저장하는 HashSet을 이용해 후보키 조합으로 뽑아진 튜플 저장 
			String[] keys = list.get(i).split("");

			for(int j = 0; j < relation.length; j++) {
				String r = "";

				for(int k = 0; k < keys.length; k++) {
					r += relation[j][Integer.parseInt(keys[k])];
				}
				set.add(r);
			}

			if(set.size() == tuple) { //전체 튜플의 수와 후보키 조합으로 뽑아진 튜플의 수가 같다면 후보키 유일성 통과 
				// 후보키 최소성 판별 
				// containsAll 메서드 사용하기 위해 List 사용
				// 기존의 String의 contains 메서드 쓰면 123, 13을 포함하지 않음으로 판별하기 때문 
				List<String> cKey = Arrays.asList(list.get(i).split("")); 

				boolean flag = true;
				for(int j = 0; j < candidateKeys.size(); j++) {
					if(cKey.containsAll(candidateKeys.get(j))) { // 후보키 리스트에 부분집합으로 있다면 최소성 만족 X
						flag = false;
						break;
					}
				}

				if(flag) { // 어떠한 부분집합으로라도 없다면 최소성 통과 
					candidateKeys.add(cKey);
				}
			}
		}

		// 유일성과 최소성 판별을 통과한 후보키만을 담고 있는 후보키 리스트의 사이즈가 바로 정답 
		return candidateKeys.size();
    }
    
    	public static void comb(boolean[] visited, int start, int r) {
		if(r == 0) {
			String num = "";
			for(int i = 0; i < visited.length; i++) {
				if(visited[i]) {
					num = num + i;
				}
			}

			list.add(num);

			return;
		} else {
			for(int i = start; i < visited.length; i++) {
				visited[i] = true;
				comb(visited, i + 1, r - 1);
				visited[i] = false;
			}
		}
	}
}

GITHUB

github.com/KwonMinha/Programmers/blob/master/2019_Kakao_Blind_Recruitment/src/CandidateKey.java

KwonMinha/Programmers