[ 알고리즘 ] 코딩 - Programmers - 후보키.java

---

문제 링크

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

코딩테스트 연습 - 후보키

---

* 프로그래머스 - Level2 - (자바)후보키 - HashSet과 HashMap을 이용한 중복제거

입력 예시

HashSet에 익숙하지 않아 많이 당황한 문제!

여러가지 자료구조에 더 많이 익숙해져야겠다!

---

< 로직 >

* 행렬의 길이만큼의 후보키 조합이 나온다.

* 1개 ~ n개까지의 후보키 조합을 만들어서 중복 선택이 되었는지 체크

* 후보키들의 중복 체크는 HashSet<Integer>를 이용

* HashSet에는 각 열의 인덱스가 담기게 된다.

* 선택한 후보키들(선택한 열)이 실제 중복선택을 하지 않는지 체크

* 이 체크는 HashMap<String, String>을 이용

---

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * 나중에 시간을 내서라도 다시 꼭 곡 꼭
 * 다시 풀어보고 어떤 로직인지 기억하기.
 * HashSet 사용하는 방법과
 * ArrayList에 HashSet<Integer>형식 쓰는 거도 익숙해지기
 * */
public class 후보키 {
	static class Solution {
		ArrayList<HashSet<Integer>> candidateKeys;
		int Answer;
	    public int solution(String[][] relation) {
	    	candidateKeys = new ArrayList<>();
	    	int n = relation[0].length;
	    	
	    	HashSet<Integer> keys = new HashSet<>();
	    	
	    	// 1개 ~ n개까지의 조합을 뽑아내자
	    	for(int i = 1; i <= n; i++) {
	    		combination(0, 0, i, keys, n, relation);
	    	}
	    	
	        return Answer;
	    }

		// 부분 집합
		private void combination(int idx, int start, int keysize, HashSet<Integer> keys, int n, String[][] relation) {
			if(idx == keysize) {
				
				// 중복 선택 방지
				for(HashSet<Integer> key : candidateKeys) {
					if(keys.containsAll(key)) return ;
				}
				
				int count = 0;
				HashMap<String, String> map = new HashMap<>();
				for(int i = 0; i < relation.length; i++) {
					StringBuilder sb = new StringBuilder();
					for(int k : keys) { // 선택한 인덱스 체크
						sb.append(relation[i][k]);
					}
					if(map.containsKey(sb.toString())) return; // 중복 선택시 멈춤
					map.put(sb.toString(), sb.toString());
					
					count++;
				}
				
				// 중복 선택 없이 구별이 가능한 경우
				// 후보키 리스트에 저장
				if(count == relation.length) {
					candidateKeys.add(keys);
					Answer++;
				}
				
				return ;
			}
			for(int i = start; i < n; i++) {
				HashSet<Integer> selectedKeys = new HashSet<>(keys);
				selectedKeys.add(i);
				combination(idx+1, i+1, keysize, selectedKeys, n, relation);
			}
		}
	}