접근
이 문제는 키를 모든 경우의 수로 만듭니다.
단, AB와 BA는 같은 키이기 때문에 백트랙킹과 시작하는 지점을 기억해야합니다.
따라서 저는 다음과 같은 방법으로 접근했습니다.
- DFS로 모든 경우의 키를 만든다. 단, 예를 들어 AB와 BA는 같기 때문에 앞에 언급된 키는 다시 불러오지 않는다.
static void dfs(int cnt, int start, int level, String answer) {
if(level==cnt){
return;
}else{
for(int i=start;i<cnt;i++){
if(!visited[i]){
visited[i]=true;
dfs(cnt,i,level+1,answer+i);
result.add(answer+i);
visited[i]=false;
}
}
}
}- 최소성을 만족시키기 위해서 키를 길이 순으로 정렬한다.
Comparator<String> comp = new Comparator<>(){
public int compare(String s1, String s2){
return s1.length() -s2.length();
}
};- 이제 유일성을 만족시키기 위해서 각 키에 대해서 tuple이 중복되지 않는지 검사한다.
이 때 Set을 만들어서 Set의 size와 튜플의 개수가 같다면 유일성을 만족한다.
// 3. 유일성을 위해 set
for(int j=0;j<relation.length;j++){
StringBuilder sb = new StringBuilder();
for(char c : charArr){
sb.append(relation[j][c-'0']).append(" ");
}
set.add(sb.toString());
}
if(set.size()==tuple && !check(r,key)){
key.add(r);
System.out.println("후보키:"+r);
}
}-
최소성을 만족시키기 위해서 "A"를 제외한 "A"가 들어가 모든 키를 제거한다.
이 4번 과정에서 저는 시간을 많이 낭비했습니다.
아래와 같이 java 8에 도입된 removeIf를 사용했는데if(set.size()<tuple){ result.removeIf(item-> item.contains(r)); }ConcurrentModificationException이 발생했습니다.
Exception in thread "main" java.util.ConcurrentModificationException at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1013) at java.base/java.util.ArrayList$Itr.next(ArrayList.java:967) at Solution.solution(Unknown Source) at SolutionTest.lambda$main$0(Unknown Source) at SolutionTest$SolutionRunner.run(Unknown Source) at SolutionTest.main(Unknown Source)이 예외는
Note that this exception does not always indicate that an object has been concurrently modified by a different thread. If a single thread issues a sequence of method invocations that violates the contract of an object, the object may throw this exception. For example, if a thread modifies a collection directly while it is iterating over the collection with a fail-fast iterator, the iterator will thow this exception
위와 같이 설명되어 있습니다.
아무래도 i번째를 삭제할 때 i+1번째가 i번째로 당겨오게 되면서 그에 다른 검사가 누락되어 발생되는 것으로 보입니다.사실 removeIf는 자바 8에 도입되었는데 Iterator의 불편함을 개선시키기 위해서 도입되었다고 했습니다. 즉 아래의 예시처럼 복잡한 코드를 한줄로 끝낼 수 있습니다.
Iterator<String> iter = li.iterator(); while(iter.hasNext()){ if(iter.next().equalsIgnoreCase("str3")) iter.remove(); }제가 저와 같은 상황으로 stack overflow에 올려진 글을 보았는데
이상하게도 removeIf나 Iterator를 이용하라고 했습니다.
하지만 여전히 ConcurrentModificationException이 발생되었습니다.
(원인을 알고 계시다면 댓글 부탁드립니다.)그래서 직접 그냥 구현하기로 했습니다.
4번 과정은 그래서 아래와 같이
현재 후보키로 들어갈 미래의 키가 현재 후보키로 등록된 키의 일부를 가지고 있는지
검사하는 메서드입니다.static boolean check(String r ,ArrayList<String> key){ int cnt =0; // 후보키로 등록된 키 k for(String k : key){ cnt =0; String[] kArr = k.split(""); for(String kIndex : kArr){ //미래의 키 r이 후보키 k의 일부를 가지고 있다면 cnt+1 if(r.contains(kIndex)) cnt++; } // 후보키 k 모두를 미래의 키 r이 가지고 있다면 true; if(cnt==k.length()){ return true; } } return false; }
풀이
import java.util.*;
class Solution {
static boolean[] visited ;
static ArrayList<String> result ;
static ArrayList<String> key ;
public int solution(String[][] relation) {
int answer = 0;
//후보키에 대한 고민
// 유일성 + 최소성: 꼭 필요한 속성들로만
// 이미 발견된 후보키가 다른 곳에 중복해서 들어갈 수 없음
// 모든 문자열은 알파벳 소문자와 숫자
// 모든 튜플은 유일하게 식별 가능 즉 중복되는 튜플은 없다.
//1. 모든 경우의 수 만들기
//2. 앞에서부터 시작해서 만약에 겹치는 후보키가 있다면 빼기
//3. 최종 개수 구하기
//튜플의 수
int tuple = relation.length;
// 경우의 수 조합을 위한 개수
int cnt = relation[0].length;
visited = new boolean[cnt];
result = new ArrayList<String>();
key = new ArrayList<String>();
//dfs 로 경우의 수 하기
dfs(cnt,0,0,"");
System.out.println("포함여부 124.contains(14)"+"124".contains("14"));
// 후보키 정렬하기
Comparator<String> comp = new Comparator<>(){
public int compare(String s1, String s2){
return s1.length() -s2.length();
}
};
// 짧은 배열부터 검사하기 위해서 정렬
Collections.sort(result,comp);
for(String r : result){
char[] charArr = r.toCharArray();
Set<String> set = new HashSet<>();
for(int j=0;j<relation.length;j++){
StringBuilder sb = new StringBuilder();
for(char c : charArr){
sb.append(relation[j][c-'0']).append(" ");
}
set.add(sb.toString());
}
if(set.size()==tuple && !check(r,key)){
key.add(r);
System.out.println("후보키:"+r);
}
}
return key.size();
}
static void dfs(int cnt, int start, int level, String answer) {
if(level==cnt){
return;
}else{
for(int i=start;i<cnt;i++){
if(!visited[i]){
visited[i]=true;
dfs(cnt,i,level+1,answer+i);
result.add(answer+i);
visited[i]=false;
}
}
}
}
static boolean check(String r ,ArrayList<String> key){
int cnt =0;
for(String k : key){
cnt =0;
String[] kArr = k.split("");
for(String kIndex : kArr){
if(r.contains(kIndex)) cnt++;
}
if(cnt==k.length()){
return true;
}
}
return false;
}
}