문제
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.
- 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
- 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
- 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
- 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.
인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.
예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.
코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?
물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.코딩테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가? 코딩테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가? backend 직군을 선택했고, senior 경력이면서 코딩테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가? 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가? 코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?
즉, 개발팀에서 궁금해하는 내용은 다음과 같은 형태를 갖습니다.
[조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?
코드
import java.util.*;
import java.util.stream.*;
class Solution {
public static int[] solution(String[] info, String[] query) {
Map<String, List<Integer>> map = new HashMap<>();
for (String s : info) {
StringTokenizer st = new StringTokenizer(s);
String language = st.nextToken();
String position = st.nextToken();
String level = st.nextToken();
String favorite = st.nextToken();
int score = Integer.parseInt(st.nextToken());
addToMap(new String[]{language, position, level, favorite}, "", score, map, 0);
}
map.values().forEach(Collections::sort);
List<Integer> answer = new ArrayList<>();
for (String s : query) {
s = s.replaceAll(" and ", " ");
StringTokenizer st = new StringTokenizer(s);
s = String.join("", st.nextToken(), st.nextToken(), st.nextToken(), st.nextToken());
int score = Integer.parseInt(st.nextToken());
answer.add(binarySearch(map.getOrDefault(s, new ArrayList<>()), score));
}
return answer.stream().mapToInt(o -> o).toArray();
}
public static int binarySearch(List<Integer> scores, int x) {
int start = 0;
int end = scores.size();
int upperBound = -1;
while (start < end) {
int mid = (start + end) / 2;
if (scores.get(mid) < x) {
upperBound = mid;
start = mid + 1;
}
if (scores.get(mid) >= x)
end = mid;
}
return scores.size() - upperBound - 1;
}
public static void addToMap(String[] queries, String s, int score, Map<String, List<Integer>> map, int index) {
if (index == 4) {
List<Integer> list = map.getOrDefault(s, new ArrayList<>());
list.add(score);
map.put(s, list);
return;
}
addToMap(queries, s + queries[index], score, map, index + 1);
addToMap(queries, s + "-", score, map, index + 1);
}
}해결 과정
-
처음에는 각 조건을 키, 원본 문자열을 값으로 저장해서 Stream API의 filter(set::contains)를 사용했다. 하지만 몇몇 테스트 케이스를 실패했다. 대체 왜...?? 이유는 계속해서 찾는 중이다.
-
결국 조건으로 나올 수 있는 쿼리문들을 키, 원본 문자열의 점수들이 담긴 리스트를 값으로 저장했다. 이렇게 하면 쿼리를 그대로 Map에서 값을 가져올 수 있다.
값을 가져와서 선형탐색 -> 시간 초과.
값을 가져와서 이진탐색 -> 부분적으로 시간 초과.
쿼리를 날리기 전에 map.values().forEach(Collections::sort) 구문으로 모든 리스트들을 정렬해두고 이진 탐색 -> 통과... -
사실 Map<String, List<Integer>>의 형태에서 Value를 다룰 때 착각해서 고생을 했다. List 등의 객체를 get()해서 가져와서 사용하면, Call by Value 식으로 가져오는 것이 아니기 때문에(물론 주소를 복사한다는 점에서는 Call by Value이다) Map 안에 저장된 값도 당연히 바뀐다. 이것을 잊고 밖에서 가공했다가 원본을 나도 모르게 훼손시켜서 계속 틀렸다ㅠㅠ
-
😁
渽晛