반응형
구현하는데 있어 상당히 복잡하게 구현을 이룬 문제였다.
이문제는 최소성과 유일성을 만족시키는 후보키를 구하는 문제이다. 맨처음 컬럼의 수를 확인했는데 최대 8이기 때문에 조합으로 풀생각을 하였다. 전체 N개에서 1개부터 N개까지 선택하는 모든 경우를 다따져보았다. 그리고 그 상황에서 hashSet을 이용하여 유일성을 확인하였고, 또다른 hashSet을 이용하여 최소성을 만족하는지 확인하였다. hashSet이 상당히 여러개가 쓰였기에 구현하는데 있어서 많이 복잡하였다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
package programmers;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class Solution_2019_카카오_후보키 {
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"}};
// String[][] relation= {{"a","b","c"},
// {"1","b","c"},
// {"a","b","4"},
// {"a","5","c"}};
// String[][] relation= {{"a","1","4"},
// {"2","1","5"},
// {"a","2","4"}};
String[][] relation= {{"b","2","a","a","b"},
{"b","2","7","1","b"},
{"1","0","a","a","8"},
{"7","5","a","a","9"},
{"3","0","a","f","9"}};
System.out.println(solution(relation));
}
static int answer;
static int R,C;
static int[] arr;
static int[] result;
static boolean[] visit;
static Set<String> allCase;
static int solution(String[][] relation) {
answer = 0;
R=relation.length;
C=relation[0].length;
arr=new int[C];
for(int i=0;i<C;i++)
arr[i]=i;
allCase=new HashSet<>();
for(int i=1;i<=C;i++) {
result=new int[i];
visit=new boolean[C];
Set<String> turn=new HashSet<>();
comb(0,0,i,relation,turn);
for(String str :turn)
allCase.add(str);
}
return answer;
}
static void comb(int start,int depth,int destination,String[][] relation,Set<String> turn) {
if(depth==destination) {
// System.out.println(Arrays.toString(result));
StringBuilder sb=new StringBuilder();
for(int index:result) { //현재들어올 인덱스들
sb.append(index+"");
}
for(String str:allCase) {
int count=0;
for(int i=0;i<str.length();i++) {
if(sb.toString().contains(str.charAt(i)+"")) {
count+=1;
}
}
if(count==str.length())
return;
}
findAnswer(relation,turn);
return;
}
for(int i=start;i<C;i++) {
if(visit[i]==false) {
visit[i]=true;
result[depth]=arr[i];
comb(i,depth+1,destination,relation,turn);
visit[i]=false;
}
}
}
static void findAnswer(String[][] relaton,Set<String> turn) {
Set<String> check=new HashSet<>();
for(int i=0;i<R;i++) {
StringBuilder sb= new StringBuilder();
for(int index : result ) {
sb.append(relaton[i][index]);
}
check.add(sb.toString());
}
if(R==check.size()) {
// System.out.println(R+","+check.size());
// System.out.println(Arrays.toString(result));
answer+=1;
StringBuilder sb= new StringBuilder();
for(int index:result) {
sb.append(index+"");
}
turn.add(sb.toString());
}
}
}
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
package programmers;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Solution_2019카카오_후보키_2 {
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));
}
static int R,C;
static boolean[] visit;
static int[] pick; //컬럼선택
static int[] arr;
static int result;
static List<String> list;
static int solution(String[][] relation) {
R=relation.length;
C=relation[0].length;
result=0;
arr=new int[C];
list=new ArrayList<>();
for(int i=0;i<C;i++)
arr[i]=i;
for(int finalDepth=1;finalDepth<=C;finalDepth++) {
pick=new int[finalDepth];
visit=new boolean[C];
comb(0,0,finalDepth,relation);
}
return result;
}
static void comb(int start,int depth,int finalDepth,String[][] relation) {
if(depth==finalDepth) {
// System.out.println(Arrays.toString(pick));
if(check(relation)==true) {
result+=1;
}
return;
}
for(int i=start;i<C;i++) {
if(visit[i]==false) {
visit[i]=true;
pick[depth]=arr[i];
comb(i,depth+1,finalDepth,relation);
visit[i]=false;
}
}
}
static boolean check(String[][] realtion) {
//유일성 체크
Set<String> set = new HashSet<>();
for(int i=0;i<R;i++) {
String str = "";
for(int c : pick) {
str=str+realtion[i][c];
}
set.add(str);
}
if(set.size()!=R)
return false;
//최소성 체크
for(String temp : list) {
int target= temp.length();
int count=0;
for(int c : pick) {
for(int i=0;i<target;i++) {
if(c== temp.charAt(i)-'0') {
count++;
}
}
}
if(count==target)
return false;
}
String str="";
for(int c : pick) {
str=str+c;
}
list.add(str);
return true;
}
}
|
반응형
'Algorithm' 카테고리의 다른 글
| [BOJ] 2003. 수들의 합2 (0) | 2020.05.11 |
|---|---|
| [BOJ] 16236. 아기 상어 (0) | 2020.05.11 |
| [Programmers] 캐시 (0) | 2020.05.08 |
| [JO] 1681. 해밀턴 순환 회로 (0) | 2020.05.08 |
| [BOJ] 4195. 친구 네트워크 (0) | 2020.05.07 |