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

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

코딩테스트 연습 - 후보키

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

class Solution {
		int []arr;
		List<String> key;
	    public int solution(String[][] relation) {
	        int col=relation[0].length;
	        int row=relation.length;
	        arr=new int[col];
	        key=new ArrayList<>();
	        
	        for(int i=1; i<=col; i++) {
	        	combination(0,0,i,col,row,relation);
	        }
	        return key.size();
	    }

		private void combination(int cnt, int start, int end, int col, int row, String[][] relation) {
			if(cnt==end) {
				String checkKey="";
				for(int i=0; i<end; i++) {
					checkKey+=arr[i];
				}
				
				if(!minimality(end,checkKey)) return; //최소성 체크 
				uniqueness(end,col,row,relation,checkKey); //유일성 체크
				return;
			}
			for(int i=start; i<col; i++) {
				arr[cnt]=i;
				combination(cnt+1, i+1,end, col, row,relation);
			}
		}

		private void uniqueness(int end, int col, int row, String[][] relation, String checkKey) {
			Set<String> tmpKey = new HashSet<>();
			
			for(int i=0; i<row; i++) {
				String str="";
				for(int j=0; j<end; j++) {
					str+=relation[i][arr[j]];
				}
				tmpKey.add(str);
			}
			if(tmpKey.size()==row) key.add(checkKey); //유일성만족
			return;
		}

		private boolean minimality(int end, String checkKey) {
			int size=key.size();
			
			for(int i=0; i<size; i++) {
				String cKey=key.get(i);
				int len=cKey.length();
				int cnt=0;
				for(int j=0; j<cKey.length(); j++) {
					if(checkKey.contains(cKey.substring(j, j+1))) cnt++;
				}
				if(len==cnt) return false;
			}
			return true;
		}
	}

소요시간 : 1시간

 

Level2문제라기에는 너무 어렵습니다....

 

일단 로직을 살펴보면 

 

·최소성 

key라는 List에 String으로 현재 후보키들이 있습니다.

현재 keyList에 있는 여러개의 key중 하나의 key가  조합으로 얻은 col에 모두 포함된다면 최소성에 위배됩니다.

예를 들어 현재 keyList에 (1,2)가 들어있습니다. 

조합으로 얻은 col의 조합이 1,2,3 이라면  1,2,3 안에는 (1,2)가 모두 포함되기 때문에 최소성 위배

하지만 col의 조합이 2,3 이라면 (1,2) 가 2,3에 모두 포함되는 것은 아니기 때문에 최소성을 만족합니다.

->이부분에서 실수를 해서 시간을 많이 잡아먹었습니다.

 

·유일성

유일성을 체크하기 위해 현재 조합으로 얻은 컬럼의 값들을 String으로 모두 더했습니다.

만약 

1 a

b b

4 c

이라면 

1행 : 1a

2행 : bb

3행 : 4c

이런식으로 String으로 더해서 Set에 넣어줍니다! 

Set의 크기와 row의 크기가 같다면 중복이 일어나지 않은것이기 때문에 유일성을 만족한다 라고 판단하였습니다!

 

너무 어려운 문제였습니다...