[프로그래머스][JAVA] 순위 검색 (인덱싱, 이진 탐색, 비트마스크)
참고 : https://www.youtube.com/watch?v=eBQtFteduyw&t=572s
인덱싱 + 이진 탐색에 대한 이해가 조금 필요한 문제임
인덱싱은 참고 유튜브 보면서 이해했고
( - 하이픈이 해당 정보에 무엇이 와도 상관이 없음인데 이것도 인덱스에 추가해서 정보를 받을 때,
ex) "java backend junior pizza 150"
위의 신입 사원 정보를 받을 때
"java backend junior pizza 150"
"java backend junior - 150"
"java backend - pizza 150"
"java backend - - 150"
"java - junior pizza 150"
"java - junior - 150"
"java - - pizza 150"
"java - - - 150"
"- backend junior pizza 150"
"- backend junior - 150"
...
" - - - - 150"
이런 식으로 개발언어/직군/경력/소울푸드가
( java 또는 - / backend 또는 - / junior 또는 - / pizza 또는 - )
이렇게 해서 2^4(16)번 넣어줌
로 모든 경우의 수에 전부 score 150점 넣어줘서 나중에 query문을 받을 때
쓸데 없이 탐색하지 않게 해주는 방식이 너무나도 놀라웠다
이진 탐색은 Line:66~75인데
원하는 score가 없는 경우 음수가 나오는데 이걸 처리해주면 되고
원하는 score가 있기는 한데 이것이 중복된 값들 중 (중복된 값이 있다고 가정할 때)
어느 위치에 있는지 모르기 때문에 중복된 값들 중 가장 왼쪽의 인덱스를 찾아야 한다
찾고 List.size() - index해주면 score이상의 값이 나오게됨
|
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
|
import java.util.*;
class Solution {
private static List<List<Integer>> scoreList;
private static Map<String, Integer> wordMap;
public int[] solution(String[] infos, String[] querys) {
// List<Integer> list =
// Arrays.asList(new Integer[]{1,3,5,6,6,6,6,6,6,6,8,10});
// int ret = Collections.binarySearch(list,6);
// ret = (ret>=0)? ret : -(ret+1);
// System.out.println(ret);
scoreList = new ArrayList<>();
wordMap = new HashMap<>();
initWordMap();
for(int i=0; i<4*3*3*3; i++){
scoreList.add(new ArrayList<>());
}
for(String info : infos){
String[] word = info.split(" ");
int score = Integer.parseInt(word[4]);
int[] smallIndex = {
wordMap.get(word[0])*3*3*3, // 개발언어
wordMap.get(word[1])*3*3, // 직군
wordMap.get(word[2])*3, // 경력
wordMap.get(word[3]) // 소울푸드
};
for(int i=0; i<(1<<4); i++){
int index = 0;
for(int j=0; j<4; j++){
if( (i&(1<<j)) !=0){
index += smallIndex[j];
}
}
scoreList.get(index).add(score);
}
}
for(int i=0; i<4*3*3*3; i++){
Collections.sort(scoreList.get(i));
}
int[] answer = new int[querys.length];
for(int i=0; i<querys.length; i++){
String[] word = querys[i].split(" ");
int score = Integer.parseInt(word[7]);
int index =
wordMap.get(word[0])*3*3*3+ // 개발언어
wordMap.get(word[2])*3*3+ // 직군
wordMap.get(word[4])*3+ // 경력
wordMap.get(word[6]); // 소울푸드
// System.out.println("index "+index);
// scoreList.get(index).forEach(s->{
// System.out.print(s+" ");
// });
// System.out.println();
// System.out.println();
List<Integer> currList = scoreList.get(index);
int findedIndex = Collections.binarySearch(currList, score);
if(findedIndex<0){
findedIndex = -(findedIndex+1);
}
else{
while(0<=findedIndex-1
&& currList.get(findedIndex-1)==score){
findedIndex--;
}
}
answer[i] = currList.size()-findedIndex;
}
// for(int i=0; i<scoreList.size(); i++){
// System.out.println(i);
// scoreList.get(i).forEach(score -> {
// System.out.print(score+" ");
// });
// System.out.println();
// }
return answer;
}
private void initWordMap(){
wordMap.put("-",0);
wordMap.put("cpp",1);
wordMap.put("java",2);
wordMap.put("python",3);
wordMap.put("backend",1);
wordMap.put("frontend",2);
wordMap.put("junior",1);
wordMap.put("senior",2);
wordMap.put("chicken",1);
wordMap.put("pizza",2);
}
}
|
cs |