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

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

코딩테스트 연습 - 후보키

import java.util.HashMap;
import java.util.HashSet;
class Solution {
		public int solution(String[][] relation) {
			
			HashMap<String, String> key=new HashMap<>();
//			System.out.println(key.size());
			int []combiArr=new int[10];
//			System.out.println(relation.length);
//			System.out.println(relation[0].length);
			for(int i=1; i<=relation[0].length; i++) { //1부터 컬럼길이만큼 1~8
				combination(key,combiArr, relation, 0,0, i);
			}
			return key.size();
		}

		private void combination(HashMap<String, String> key, int[] combiArr, String[][] relation, int cnt, int start, int end) {
			if(cnt==end) {
//				System.out.println(Arrays.toString(combiArr));
//				System.out.println("d");
				//후보키 될려는게 뭐인지 알아내고
				StringBuilder sb= new StringBuilder();
				for(int i=0; i<end; i++) {
					sb.append(combiArr[i]);
				}

				// 최소성 만족해야함
				if(!Minimalism(combiArr,relation,end,key,sb.toString())) return;

				
				//유일성 체크 튜플들을 다 더해서 set에 있는지 없는지 확인 
				if(!unique(combiArr,relation,end)) return;
				
				
//				System.out.println(sb.toString());
				//후보키에 추가해주기
				key.put(sb.toString(), "1");
				
				return;
			}
			for(int i=start; i<relation[0].length; i++) {
				combiArr[cnt]=i;
				combination(key, combiArr, relation, cnt+1, i+1, end);
				
			}
		}

		private boolean Minimalism(int[] combiArr, String[][] relation, int end, HashMap<String, String> key, String candidateKey) {
			for(String realKey:key.keySet()) {
				int cnt=0;
				for(int i=0; i<realKey.length(); i++) {
					if(candidateKey.contains(String.valueOf(realKey.charAt(i)))) cnt++;
					
				}
				if(cnt==realKey.length()) return false;
				
			}
			return true;
		}

		private boolean unique(int[] combiArr, String[][] relation, int end) {
			HashSet<String> set= new HashSet<>();
			
			for(int i=0; i<relation.length; i++) {
				StringBuilder sb= new StringBuilder();
				for(int j=0; j<end; j++) {
					sb.append(relation[i][combiArr[j]]);
				}
				
				if(sb.toString().equals("")) continue;
				if(set.contains(sb.toString())) return false;
				set.add(sb.toString());
			}
			// TODO Auto-generated method stub
			return true;
		}
	}

소요시간 : 1시간 21분

 

 

우선 조합을 돌려서 1~컬럼의 개수만큼의 조합을 돌려줍니다.

 

각각 컬럼의 조합이 완성될 때마다

 

유일성과  최소성을 확인합니다.

 

유일성

- 각 행을 돌면서 조합에서 뽑은 컬럼을 StringBuilder로 appned 해줍니다.

- 각 행에서  append가 끝났으면 set에서 확인을 합니다. 만약 contians로 확인을 했는데 값이 이미 있다면 유일성 만족 x

 

최소성

- 우선 지금까지 구한 키를 순회합니다.

- 하나의 키를 꺼내서 charAt으로 하나씩 돌아줍니다

- 이때 현재 조합을 통해 구한 컬럼의 조합에 포함되는 charAt이 있다면 cnt를 ++ 해줍니다.

- 만약 charAt을 다 돌았을 때 cnt가 키의 길이와 같다면 최소성을 만족하지 못합니다.

 

ex) 현재까지 구한 키 : {1 2}

     조합으로 구한 키 : {0 2 3}

 

1 -> 조합으로 구한 키에 속하지 않으므로 skip

2 -> 조합으로 구한 키에 속하므로 cnt++

cnt는 1입니다.  고로 ( 1!= 2) 이므로 최소성을 만족합니다.

 

 

ex) 현재까지 구한 키 {1 3}

     조합으로 구한 키 {1 2 3}

 

1-> 포함 cnt++

3 -> 포함 cnt++

 

즉  (2==2) 이므로 최소성을 만족하지 못합니다.

 

 

중간에 배열 돌릴 때 i <relation [0]. length로 범위를 잡아야 하는데  i <relation [i]. length로 잡아서 런타임 에러가 났습니다.

.... 이거 잡는데 한 40분 쓴 듯  다음부터는 배열 row, col로 바꿔서 쓰는 습관을 들여야겠습니다.

끝~