[프로그래머스] 후보키

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

프로그래머스

---

후보키의 조건은

1) 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.

2) 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

그래서 저는 먼저 속성의 조합이 만들어질 수 있는 모든 경우의 수를 뽑아서 뽑힌 속성들이 테이블에서 유일성을 만족시키는지 판단했습니다. 그런 후에는 최소성을 만족시키기 위해 ArrayList answer 에는 뽑힌 후보키들과 비교하여 후보키를 선택했습니다.

여기서 헷갈렸던 점은 뽑힌 앞서 후보키의 조합이 0 2 라고 가정한다면 0 3 4 도 후보키가 될 수 있다는 점이었습니다. 처음에는 두가지 경우에서 0이 겹치기 때문에 후보키가 될 수 없다고 생각했는데 0 2 가 완전이 포함 되는 0 2 3 경우에만 후보키가 될 수 없는 것이었습니다. 이 부분을 주의해서 풀면 정답을 구할 수 있습니다.

[ 문제 풀이 ]

1. recur() 메소드를 통해서 뽑힐 수 있는 모든 속성의 조합을 구합니다.

2. 속성이 1~N개까지 뽑힐 때 마다 checking() 이라는 함수를 통해서 list에 유일성을 만족시키는 예비 후보키들을 저장합니다.

3. list에는 유일성을 만족시키는 예비 후보키들이 저장되어 있고, filtering() 을 통하여 최소성을 만족시키는지 검사합니다.

4. 최소성을 만족시킨다면 answer에 저장하고 마지막에 answer의 크기를 출력하면 정답입니다.

---

package test;

import java.util.ArrayList;

public class Solution {

	static int N, M, L;
	static int[] temp;
	static boolean[] mask;
	static String[][] rel;
	static ArrayList<String> list, answer;
	static StringBuilder sb;

	public static int solution(String[][] relation) {
		answer = new ArrayList();

		N = relation[0].length;
		M = relation.length;

		rel = new String[M][N];

		for (int i = 0; i < M; i++)
			for (int j = 0; j < N; j++)
				rel[i][j] = relation[i][j];

		temp = new int[N + 1];
		mask = new boolean[N + 1];
		temp[0] = 1;

		for (int i = 1; i <= N; i++) {
			L = i;
			list = new ArrayList();
			recur(1, 0);
			filtering();
		}

		return answer.size();
	}

	public static void filtering() {

		for (int i = 0; i < list.size(); i++) {
			for (int j = 0; j < answer.size(); j++) {
				int a = 0;
				for (int k = 0; k < answer.get(j).length(); k++) {
					if (list.get(i).contains("" + answer.get(j).charAt(k))) {
						a++;
					}
				}
				if (answer.get(j).length() == a) {
					list.remove(i);
					i--;
					break;
				}
			}
		}

		for (int i = 0; i < list.size(); i++) {
			answer.add(list.get(i));
		}
	}

	public static void recur(int start, int depth) {
		if (depth == L) {

			// temp 에 확인할 열의 인덱스가 들어있다.
			checking();

			return;
		}
		for (int i = temp[start - 1]; i <= N; i++) {
			if (mask[i])
				continue;
			temp[start] = i;
			mask[i] = true;
			recur(start + 1, depth + 1);
			mask[i] = false;
		}
	}

	public static void checking() {

		for (int i = 0; i < M; i++) {
			String st1 = "";
			for (int select = 1; select <= L; select++)
				st1 += rel[i][temp[select] - 1];

			for (int j = i + 1; j < M; j++) {
				String st2 = "";
				for (int select = 1; select <= L; select++)
					st2 += rel[j][temp[select] - 1];

				if (st1.equals(st2)) {
					return;
				}
			}
		}

		sb = new StringBuilder();

		for (int i = 1; i <= L; i++) {
			sb.append(temp[i] - 1);
		}

		list.add(sb.toString());

	}
}