[java] 프로그래머스 - 후보키

문제

프로그래머스-후보키
주어진 릴레이션에서 유일성과 최소성을 만족하는 후보키의 최대 개수를 구하는 문제

• 제한 사항

relation : 2차원 문자열 배열
relation의 컬럼 길이 : 1이상 8이하
relation의 로우 길이 : 1이상 20이하
relation의 모든 문자열 길이 : 1이상 8이하, 알파벳 소문자와 숫자로 구성
relation의 모든 튜플은 유일하게 식별 가능

• 예시
  
  첫번째 칼럼 [학번]은 유일성을 만족하며 후보 키가 될 수 있다
  [이름, 전공]을 함께 사용하면 유일성을 만족해 후보 키가 될 수 있다
  [이름, 전공, 학년]을 함께 사용하면 유일성을 만족하지만 최소성을 만족하지 못하므로 후보키가 될 수 없다

-> [학번, [이름, 전공]]

풀이

우선 입력받은 릴레이션에서 예시의 [학번]처럼 유일성을 만족하는 후보 키를 찾는다
예시를 기준으로 [학번]을 제외한 나머지 속성들로 부분집합을 구성한다

이 때, 부분집합에서 원소의 갯수가 1개인 것은 선택하면 안된다
왜냐?? 처음에 [학번]을 추린 것 처럼 유일성 만족 검사에서 탈락했기 때문에 원소에 속하는 것이기 때문이다
그러므로 원소가 2개 이상인 것들을 추려 chkList에 넣는다

부분 집합 생성 후 chkList를 “포함 원소의 수가 작은 순”으로 정렬한다

부분집합을 모아놓은 chkList에서 원소를 하나씩 순회한다
i번째 부분집합을 가지고 유일성을 만족하는지 확인한다
유일성을 만족하지 않는다면 다음 부분집합 확인
유일성을 만족한다면 후보키를 저장한 keys에서 현재 부분집합의 일부를 포함하는지 확인한다

예를들어,
예시처럼 0번 속성(학번)이 후보키로 먼저 선발되고,
0을 제외하고 0~3까지 원소에서 2개이상 부분집합을 구하면
[1, 2],[1, 3],[2, 3],[1, 2, 3] 을 구할 수 있다

이 때 유일성을 만족하는 것들만 모으면 [1, 2], [1, 2, 3]이 된다
원소 갯수가 작은 순으로 확인하니까 [1, 2, 3]의 차례에 keys에는 [1, 2]가 들어있다
keys에 들어있는 [1, 2]가 [1, 2, 3]에 포함되므로 [1, 2, 3]은 후보키가 될 수 없다

• 생각해 볼 문제
  [1, 2]가 [1, 2, 3]에 포함되는 것을 어떤식으로 구현할지..
  원래 처음에 생각했던건 트라이트리형태로 1 - 2 - last 넣어놓고
  [1, 2, 3]을 넣는 과정에서 last가 발견되면 후보키 등록 x 를 했는데
  [1, 3], [2, 3], [1, 2, 3] 인 경우 셋 다 가능하다고 되버려서 60점대 맞았다 ㅠㅠ

소스코드

import java.util.*;
class Solution {
static boolean[] chk;
	static int answer;
	static ArrayList<Check> keys; // 채택된 후보키
	static String[][] re; // relation
	static ArrayList<Check> chkList; // 검토해볼 부분집합
	static Set<String> set; // 유일성 확인용

	public int solution(String[][] relation) {
		answer = 0;
		chkList = new ArrayList<>();
		keys = new ArrayList<>();
		chk = new boolean[relation[0].length];
		re = relation;
		set = new HashSet<>();
		Arrays.fill(chk, true); // true로 넣어서 보통 부분집합의 반대로 동작
		int pre = 0; // 유일성을 만족하는 속성의 갯수 
		for (int i = 0; i < relation[0].length; i++) {
			set.clear();
			for (int j = 0; j < relation.length; j++) {
				set.add(relation[j][i]);
			}
			if (set.size() == relation.length) {
				answer++;
				chk[i] = false; // 부분집합에서 제외하기 위해
			}
		}
		pre = answer;
		subsum(0, 0, pre);
		chkList.sort(new Comparator<Check>() {
			@Override
			public int compare(Check o1, Check o2) { // 원소 적은 순
				return o2.cnt - o1.cnt;
			}
		});
		// 부분집합 결과가 후보키가 될 수 있는지
		for (int i = 0; i < chkList.size(); i++) {
			chkKeys(chkList.get(i), pre);
		}
		return answer;
	}

	private void subsum(int idx, int cnt, int pre) {
		if (idx == chk.length) {
			if (cnt >= chk.length - pre - 1) // 원소 2개이하 부분집합은 종료
				return;
			chkList.add(new Check(chk.clone(), cnt));
			return;
		}
		if (!chk[idx])
			subsum(idx + 1, cnt, pre);
		else {
			chk[idx] = false;
			subsum(idx + 1, cnt + 1, pre);
			chk[idx] = true;
			subsum(idx + 1, cnt, pre);
		}

	}

	private void chkKeys(Check curr, int pre) {
		boolean[] chk = curr.chk;
		StringBuilder sb;
		set.clear();
		for (int j = 0; j < re.length; j++) {
			sb = new StringBuilder();
			for (int k = 0; k < chk.length; k++) {
				if (chk[k])
					sb.append(re[j][k] + "|");
			}
			if (set.contains(sb.toString())) // 유일성x
				return;
			else
				set.add(sb.toString());
		}
		// 유일성 만족한다면
		if (set.size() == re.length) {
			for (Check key : keys) {
				if (key.cnt == curr.cnt) // 같은 수의 원소를 가지고있다면 판단할 필요 x
					continue;
				int trueCnt = 0;
				for (int i = 0; i < key.chk.length; i++) {
					if (key.chk[i] && curr.chk[i]) // curr과 key가 같은 원소를 가졌다면
						trueCnt++;
				}
				if (trueCnt == chk.length - key.cnt - pre)
					return;
			}
			keys.add(curr);
			answer++;
		}
	}
}

class Check {
	boolean[] chk;
	int cnt;

	public Check(boolean[] chk, int cnt) {
		super();
		this.chk = chk;
		this.cnt = cnt;
	}
}