순위 검색
https://school.programmers.co.kr/learn/courses/30/lessons/72412 (opens in a new tab)
내 풀이
Query와 Info를 하나씩 비교하면 반드시 시간초과가 난다.
class Solution {
private HashMap<Integer, String[]> infoMap = new HashMap<>();
public int[] solution(String[] info, String[] query) {
List<Integer> ans = new ArrayList<>();
// 모든 정보를 해시맵에 저장
for (int i = 0; i < info.length; i++) {
infoMap.put(i, info[i].split(" "));
}
for (String q : query) {
String[] parsedQuery = q.replace("and ", "").split(" ");
String lang = parsedQuery[0];
String pos = parsedQuery[1];
String car = parsedQuery[2];
String food = parsedQuery[3];
int point = Integer.parseInt(parsedQuery[4]);
long count = infoMap.entrySet().stream()
.filter(e -> {
String[] details = e.getValue();
return (lang.equals("-") || details[0].equals(lang)) &&
(pos.equals("-") || details[1].equals(pos)) &&
(car.equals("-") || details[2].equals(car)) &&
(food.equals("-") || details[3].equals(food)) &&
Integer.parseInt(details[4]) >= point;
})
.count();
ans.add((int) count);
}
return ans.stream().mapToInt(Integer::intValue).toArray();
}
}정답 풀이
모든 경우의 수를 key 값으로 변경한다. 예를 들자면
java, backend, junior, pizza, 100 라면 key의 종류는 아래와 같이 총 16개가 된다.
- -, -, -, -, 100
- java, -, -, -, 100
- java, backend, -, -, 100
- java, backend, junior, -, 100
- java, backend, junior, pizza, 100
...
- -, backend, junior, -, 100
- -, backend, -, -, 100
...
이 부분은 흔히 쓰이는 Combination 로직을 사용해서 구할 수 있다.
// info가 포함될 수 있는 문장
private static void makeSentence(String[] p, String str, int cnt) {
if (cnt == 4) {
if (!map.containsKey(str)) {
List<Integer> list = new ArrayList<Integer>();
map.put(str, list);
}
map.get(str).add(Integer.parseInt(p[4]));
return;
}
makeSentence(p, str + "-", cnt + 1);
makeSentence(p, str + p[cnt], cnt + 1);
}그리고 이 Qeury를 각각 key로 만들고 점수를 이분 탐색을 해서 풀어야 효율성에 통과한다.
전체 코드
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
class Solution {
static HashMap<String, List<Integer>> map;
public static int[] solution(String[] info, String[] query) {
int[] answer = new int[query.length];
map = new HashMap<String, List<Integer>>();
for (int i = 0; i < info.length; i++) {
String[] p = info[i].split(" ");
makeSentence(p, "", 0);
}
for (String key : map.keySet())
Collections.sort(map.get(key));
for (int i = 0; i < query.length; i++) {
query[i] = query[i].replaceAll(" and ", "");
String[] q = query[i].split(" ");
answer[i] = map.containsKey(q[0]) ? binarySearch(q[0], Integer.parseInt(q[1])) : 0;
}
return answer;
}
// 이분 탐색
private static int binarySearch(String key, int score) {
List<Integer> list = map.get(key);
int start = 0, end = list.size() - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (list.get(mid) < score)
start = mid + 1;
else
end = mid - 1;
}
return list.size() - start;
}
// info가 포함될 수 있는 문장
private static void makeSentence(String[] p, String str, int cnt) {
if (cnt == 4) {
if (!map.containsKey(str)) {
List<Integer> list = new ArrayList<Integer>();
map.put(str, list);
}
map.get(str).add(Integer.parseInt(p[4]));
return;
}
makeSentence(p, str + "-", cnt + 1);
makeSentence(p, str + p[cnt], cnt + 1);
}
}