공부기록
후보키 본문
- 문제
https://programmers.co.kr/learn/courses/30/lessons/42890#
코딩테스트 연습 - 후보키
[["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2
programmers.co.kr
- 코드
더보기
import java.util.*;
class Solution {
int count = 0;
public int solution(String[][] relation) {
int answer = 0;
boolean check[] = new boolean[relation[0].length];
boolean record[] = new boolean[relation[0].length];
boolean mid_rec[] = new boolean[relation[0].length];
for(int i=0; i<check.length; i++){
check[i] = false;
record[i] = false;
mid_rec[i] = false;
}
for(int i=1; i<=check.length; i++){
dfs(relation, check, record, mid_rec, 0, i);
for(int j=0; j<mid_rec.length; j++){
if(mid_rec[j]){
record[j] = mid_rec[j];
mid_rec[j] = false;
}
}
}
answer = count;
return answer;
}
boolean findAns(String[][] relation, boolean check[]){
HashMap<String, Boolean> key_count = new HashMap<>();
for(int i=0; i<relation.length; i++){
String curKey = "";
for(int j=0; j<relation[i].length; j++){
if(check[j])
curKey += (relation[i][j] + "/");
}
if(key_count.get(curKey) != null)
return false;
else
key_count.put(curKey, true);
}
return true;
}
void dfs(String[][] relation, boolean check[], boolean record[], boolean mid_rec[], int cur_idx, int left_count){
if(left_count == 0){
if(this.findAns(relation, check)){
for(int i=0; i<check.length; i++)
if(check[i])
mid_rec[i] = check[i];
count++;
}
}else if(cur_idx == check.length){
return;
}else{
if(record[cur_idx] == false){
check[cur_idx] = true;
this.dfs(relation, check, record, mid_rec, cur_idx+1, left_count-1);
check[cur_idx] = false;
}
this.dfs(relation, check, record, mid_rec, cur_idx+1, left_count);
}
}
}
더보기
import java.util.*;
class Solution {
int count = 0;
public int solution(String[][] relation) {
int answer = 0;
boolean check[] = new boolean[relation[0].length];
ArrayList<String> keyArr = new ArrayList<>();
for(int i=0; i<check.length; i++){
check[i] = false;
}
for(int i=1; i<=check.length; i++){
dfs(relation, keyArr, check, 0, i);
}
boolean his[] = new boolean[keyArr.size()];
String strArr[] = new String[keyArr.size()];
for(int i=0; i<strArr.length; i++)
strArr[i] = keyArr.get(i);
Arrays.sort(strArr, (s1, s2)->Integer.compare(s1.length(), s2.length()));
for(int i=0; i<strArr.length; i++){
if(his[i])
continue;
else
count++;
for(int j=i+1; j<strArr.length; j++){
if(strArr[j].contains(strArr[i])){
his[j] = true;
}
}
}
answer = count;
return answer;
}
boolean findAns(String[][] relation, boolean check[]){
HashMap<String, Boolean> key_count = new HashMap<>();
for(int i=0; i<relation.length; i++){
String curKey = "";
for(int j=0; j<relation[i].length; j++){
if(check[j])
curKey += (relation[i][j] + "/");
}
if(key_count.get(curKey) != null)
return false;
else
key_count.put(curKey, true);
}
return true;
}
void dfs(String[][] relation, ArrayList<String> keyArr, boolean check[], int cur_idx, int left_count){
if(left_count == 0){
if(this.findAns(relation, check)){
String curKey = "";
for(int i=0; i<check.length; i++)
if(check[i])
curKey += Integer.toString(i);
keyArr.add(curKey);
}
}else if(cur_idx == check.length){
return;
}else{
check[cur_idx] = true;
this.dfs(relation, keyArr, check, cur_idx+1, left_count-1);
check[cur_idx] = false;
this.dfs(relation, keyArr, check, cur_idx+1, left_count);
}
}
}
더보기
import java.util.*;
class Solution {
int count = 0;
public int solution(String[][] relation) {
int answer = 0;
boolean check[] = new boolean[relation[0].length];
ArrayList<Integer> keyArr = new ArrayList<>();
for(int i=0; i<check.length; i++){
check[i] = false;
}
for(int i=1; i<=check.length; i++){
dfs(relation, keyArr, check, 0, i);
}
Collections.sort(keyArr);
boolean his[] = new boolean[keyArr.size()];
for(int i=0; i<keyArr.size(); i++)
his[i] = false;
for(int i=0; i<keyArr.size(); i++){
int a = keyArr.get(i);
if(his[i])
continue;
count++;
for(int j=i+1; j<keyArr.size(); j++){
int b = keyArr.get(j);
if(a == (a&b))
his[j] = true;
}
}
answer = count;
return answer;
}
boolean findAns(String[][] relation, boolean check[]){
HashMap<String, Boolean> key_count = new HashMap<>();
for(int i=0; i<relation.length; i++){
String curKey = "";
for(int j=0; j<relation[i].length; j++){
if(check[j])
curKey += (relation[i][j] + "/");
}
if(key_count.get(curKey) != null)
return false;
else
key_count.put(curKey, true);
}
return true;
}
void dfs(String[][] relation, ArrayList<Integer> keyArr, boolean check[], int cur_idx, int left_count){
if(left_count == 0){
if(this.findAns(relation, check)){
int curKey = 0;
int cursor = 1;
for(int i=0; i<check.length; i++, cursor = cursor<<1)
if(check[i])
curKey += cursor;
keyArr.add(curKey);
}
}else if(cur_idx == check.length){
return;
}else{
check[cur_idx] = true;
this.dfs(relation, keyArr, check, cur_idx+1, left_count-1);
check[cur_idx] = false;
this.dfs(relation, keyArr, check, cur_idx+1, left_count);
}
}
}- 피드백
- 1차 시도
- 후보키들중 하나의 후보키에 이미 쓰인 값이 다른 후보키에 들어갈 수 있었다. 1차 시도는 그래서 실패
- 2차 시도
- 그래서 모든 key들을 구해서 string으로 contains해서 풀려고 했는데... 다음과 같은 경우가 있다.
- 후보키 AC, 유일성이 있는 AKC... 이 경우 AKC는 답으로 인정될 수 없지만 contains하면 AKC는 걸러지지 않아 답으로 처리해버린다.
- 중간에 있는 것 까지 처리할 수 있는 것은 결국 속성별로 idx를 주어 겹쳐지는지 확인하는 방법이고 이는 비트 마스킹으로 O(1)만에 해결할 수 있다.
- 이와 같이 연속적이지 않은 원소들의 집합을 연속적이라고 착각하지 말자.
- 1차 시도