[프로그래머스/42890/JAVA] 후보키

Kakao Blind Recruitment 2019

날짜	분류	번호	알고리즘 분류
21-03-29	프로그래머스	42890	subset	링크

문제 요약

1. 주어진 테이블에서 후보키 찾기
2. 유일성과 최소성이 보장되어야 함

 

풀이

1. dfs(subset)을 사용하여 속성의 부분집합을 전부 구함
2. 선택된 속성들만 가지고 객체를 만들어서 set에 넣음 (중복 허용X)
   • set의 크기가 처음 주어진 table의 튜플 개수와 같으면 유일성이 보장된다는 의미
3. 유일성이 보장되는 속성들의 리스트를 만듦
4. 속성들의 리스트를 크기 순으로 정렬
5. list의 크기만큼 반복문을 돌리면서 result에 있는 집합들과 비교
   • 최소성 비교
   • 최소성이 만족되는 경우에만 result에 넣음

 

비고

• 급하게 풀어서 코드가 깰꿈하지 못함 ㅠㅠ

 

package KakaoBlindRecruitment2019.P42890_후보키;

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

public class Solution {

	static List<List<Integer>> list;

	public static int solution(String[][] relation) {
		int arrlen = relation[0].length;
		list = new ArrayList<>();
		subset(0, new boolean[arrlen], arrlen, relation);

		return getMinimum();
	}

	private static int getMinimum() {
		Collections.sort(list, new Comparator<List<Integer>>() {
			@Override
			public int compare(List<Integer> o1, List<Integer> o2) {
				return o1.size() - o2.size();
			}
		});

		List<List<Integer>> result = new ArrayList<>();
		for (int i = 0; i < list.size(); i++) {
			boolean flag = true;
			for (int j = 0; j < result.size(); j++) {
				if (list.get(i).containsAll(result.get(j))) {
					flag = false;
					break;
				}

			}
			if (flag)
				result.add(list.get(i));
		}
		return result.size();
	}

	static void subset(int depth, boolean[] select, int L, String[][] relation) {
		if (depth == L) {
			Set<Tuple> set = new HashSet<>();
			for (int i = 0; i < relation.length; i++) {
				Tuple t = new Tuple();
				for (int j = 0; j < relation[i].length; j++) {
					if (select[j])
						t.attr.add(relation[i][j]);
				}
				set.add(t);
			}
			if (set.size() == relation.length) {
				List<Integer> tmp = new ArrayList<>();
				for (int i = 0; i < L; i++) {
					if (select[i])
						tmp.add(i);
				}
				list.add(tmp);
			}
			return;
		}
		select[depth] = true;
		subset(depth + 1, select, L, relation);
		select[depth] = false;
		subset(depth + 1, select, L, relation);
	}

	static class Tuple {
		List<String> attr;

		public Tuple() {
			super();
			attr = new ArrayList<>();
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + ((attr == null) ? 0 : attr.hashCode());
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Tuple other = (Tuple) obj;
			if (attr == null) {
				if (other.attr != null)
					return false;
			} else if (!attr.equals(other.attr))
				return false;
			return true;
		}

	}

	public static void main(String[] args) {
		String[][] relation = { { "100", "ryan", "music", "2" }, { "200", "apeach", "math", "2" },
				{ "300", "tube", "computer", "3" }, { "400", "con", "computer", "4" }, { "500", "muzi", "music", "3" },
				{ "600", "apeach", "music", "2" } };
		System.out.println(solution(relation));
	}

}