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

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

코딩테스트 연습 - 후보키

문제풀이

보자마자 어떻게 풀어야겠다가 바로 생각 나지 않았지만 설계를 잘하였고 문제없이 풀었다.

하지만 테스트케이스 18,19,20,22,25가 틀리면서 왜 틀리지? 생각하게 되었고 문제점을 찾게 되었다.

(이름,학년)이 유일성과 최소성을 만족하여 저장하고 있다고 하면 (이름,전공,학년)에서 (이름,학년) 때문에

최소성을 만족하지 않지만 기존 코드에서는 list에 이름+학년으로 저장하여  이름+전공+학년을

contain 하여 존재하면 처리하게 해주었다.

하지만 여기서 문제점이 가운데 전공때문에 이름+학년의 처리를 못하게 되면서 테스트 케이스를 만족 못 하였다.

하여 일일히 검사하는 코드르 바꿔 주었고 통과하게 되었다.

 

조합으로 처리해주었고, 최소성 때문에 작은 단위부터 검사해주어야 되기때문에

for문으로 조합의 길이를 증가시켜주었다. 최소성을 만족하게 되면 유일성 검사를 위해 검사할려는 튜플들을

temp 배열에 문자열을 다 더하여 따로 저장해두었다가 uniqueness함수를 통해 HashSet으로 중복을 걸러주어

만약에 중복이 없다면 HashSet의 size가 Row의 길이와 같기 때문에 유일성을 검사해주었다.

 

코드

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

class Solution {
    static int N, M;
	static List<String> list;
	static char[] isSelected;
	String[] temp;

	public int solution(String[][] relation) {
		list = new ArrayList<>();
		N = relation.length;
		M = relation[0].length;
		isSelected = new char[M];
		temp = new String[N];
		Arrays.fill(isSelected, 'n');
		
		for(int i=1; i<=M; i++) {
			combi(0,0,i, relation);
		}
		
		return list.size();
	}

	public void combi(int cnt, int start, int limit, String[][] relation) {
		if (cnt == limit) {
			String check = "";
			for (int i = 0; i < N; i++) {
				temp[i] = "";
			}
			// 최소성검사
			for (int i = 0; i < M; i++) {
				if (isSelected[i] != 'n')
					check += String.valueOf(isSelected[i]);
			}
			
			for (int i = 0; i < list.size(); i++) {
				String a = list.get(i);
				int index =0;
				for(int j =0; j<a.length(); j++) {
					String e = "";
					e += a.charAt(j);
					if (check.contains(e)) index++;
				}
				if (index == a.length()) return;
			}

			for (int i = 0; i < M; i++) {
				if (isSelected[i] == 'n')
					continue;
				for (int j = 0; j < N; j++) {
					temp[j] += relation[j][isSelected[i]-'0'];
				}
			}
			// 유일성 체크
			if (!uniqueness(temp))
				return;

			// 최소성 유일성 다 맞음
			list.add(check);
			return;
		}

		for (int i = start; i < M; i++) {
			isSelected[cnt] = (char) ('0'+i);
			combi(cnt + 1, i + 1, limit, relation);
		}
	}

	public boolean uniqueness(String[] tuples) {
		boolean ch = false;
		HashSet<String> set = new HashSet<>();
		for (int i = 0; i < N; i++) {
			set.add(tuples[i]);
		}

		if (set.size() == N)
			ch = true;

		return ch;
	}
}