Kakao Blind Recruitment 2019
날짜 | 분류 | 번호 | 알고리즘 분류 | |
---|---|---|---|---|
21-03-29 | 프로그래머스 | 42890 | subset | 링크 |
문제 요약
- 주어진 테이블에서 후보키 찾기
- 유일성과 최소성이 보장되어야 함
풀이
- dfs(subset)을 사용하여 속성의 부분집합을 전부 구함
- 선택된 속성들만 가지고 객체를 만들어서 set에 넣음 (중복 허용X)
- set의 크기가 처음 주어진 table의 튜플 개수와 같으면 유일성이 보장된다는 의미
- 유일성이 보장되는 속성들의 리스트를 만듦
- 속성들의 리스트를 크기 순으로 정렬
- 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));
}
}
'알고리즘왕 > Programmers' 카테고리의 다른 글
[프로그래머스/JAVA] 크레인 인형 뽑기 게임 (0) | 2021.05.03 |
---|---|
[프로그래머스/42889/JAVA] 실패율 (0) | 2021.03.31 |
[프로그래머스/60057/JAVA] 문자열 압축 (0) | 2021.03.29 |
[프로그래머스/42892/JAVA] 길 찾기 게임 (0) | 2021.03.29 |
[Programmers/72413/JAVA] 합승 택시 요금 (0) | 2021.03.25 |