1. 문제 요약
지원자의 4가지 스펙(언어, 직군, 경력, 소울푸드)과 코딩 테스트 점수가 info 배열로 주어집니다. 그리고 query 배열로 검색 조건(4가지 스펙 + 기준 점수)이 주어집니다.
이때, 쿼리 조건에 "-" (와일드카드)가 포함될 수 있습니다. 각 쿼리 조건에 대해, 4가지 스펙이 일치하고 코딩 테스트 점수가 기준 점수 이상인 지원자가 총 몇 명인지 찾아 배열로 반환하는 문제입니다.
info 배열의 크기는 최대 50,000, query 배열의 크기는 최대 100,000이므로, 단순 탐색으로는 시간 초과가 발생할 수밖에 없는 효율성이 매우 중요한 문제입니다.
2. 접근 방식
쿼리 요청에 빠르게 응답할 수 있도록, info 데이터를 가공하는 방법을 선택했습니다.
-
모든 경우의 수 처리: 지원자가 해당될 수 있는 모든 쿼리 조합을 미리 만듭니다. ex) "java backend junior pizza", "java backend junior -", "java backend - pizza", ..., "----"
-
HashMap 활용: HashMap<String, List>를 사용, 저장된 점수들은 오름차순 정렬
- key: 쿼리 조합
- value: 점수 리스트
-
이진 탐색: 점수 이상의 값이 처음 시작되는 위치를 탐색
3. 시도했지만 실패한 풀이
실패 원인: 정확성은 통과하였지만, 효율성 테스트 시간 초과로 통과하지 못했습니다. 이유는 info의 개수가 N, query 개수가 M일 경우 최악의 경우 50억 번의 연산이 필요하기 때문에 효율성 테스트는 통과하지 못했습니다.
import java.util.*;
import java.util.stream.*;
class Solution {
public int[] solution(String[] info, String[] query) {
// 1. info를 Person 객체 리스트로 변환
List<Person> persons = Arrays.stream(info)
.map(Person::new)
.collect(Collectors.toList());
// 2. 각 query를 순회
int[] answer = Arrays.stream(query)
.mapToInt(it->{
int count = 0;
// 3. 모든 Person을 순회하며 조건 비교 (N * M)
for(Person p : persons)
if(p.same(it))
count += 1;
return count;
})
.toArray();
return answer;
}
// 지원자 정보를 담는 클래스
class Person {
String lang;
String position;
String career;
String food;
int point;
public Person(String s){
String[] info = s.split(" ");
this.lang = info[0];
this.position = info[1];
this.career = info[2];
this.food = info[3];
this.point = Integer.parseInt(info[4]);
}
// 쿼리와 Person 정보를 비교하는 메서드
public boolean same(String query){
String[] q = query.split(" ");
boolean lang = check(this.lang,q[0]);
boolean position = check(this.position,q[2]);
boolean career = check(this.career,q[4]);
boolean food = check(this.food,q[6]);
boolean point = this.point >= Integer.parseInt(q[7]);
return lang && position && career && food && point;
}
// 와일드카드(-) 처리를 포함한 비교
private boolean check(String a, String b){
return a.equals(b) || b.equals("-");
}
}
}4. 최종 풀이 코드
해시맵 + 이진 탐색 방식으로 구현한 코드로 정확성, 효율성을 모두 통과한 코드입니다.
import java.util.*;
class Solution {
// [Key: 쿼리 조합, Value: 점수 리스트]
Map<String,List<Integer>> map = new HashMap<>();
public int[] solution(String[] info, String[] query) {
// 1. info 데이터를 기반으로 map 전처리
for(String i : info){
String[] data = i.split(" ");
// 16가지 조합을 만드는 재귀 함수 호출
recursion(0,"",data,Integer.parseInt(data[4]));
}
// 2. map의 모든 점수 리스트를 정렬 (이진 탐색을 위함)
for(List<Integer> list : map.values()){
Collections.sort(list);
}
// 3. query 처리
int[] answer = new int[query.length];
int i = 0;
for(String q : query){
String[] que = q.split(" and ");
String[] t = que[3].split(" "); // "pizza 100" 분리
// 쿼리 조건을 map의 key와 같은 형식으로 만듦
String key = que[0] + que[1] + que[2] + t[0];
int point = Integer.parseInt(t[1]);
// map에 해당 key가 없으면(일치하는 지원자 0명)
if(!map.containsKey(key)){
answer[i++] = 0;
continue;
}
// 4. 이진 탐색(Lower Bound)으로 기준 점수 이상인 첫 위치 찾기
List<Integer> list = map.get(key);
int left = 0;
int right = list.size();
while(left < right){
int mid = (left + right) / 2;
if(list.get(mid) >= point){
// 기준 점수 이상이면, 더 앞쪽도 확인
right = mid;
}else{
// 기준 점수 미만이면, 더 뒤쪽 확인
left = mid + 1;
}
}
// 5. 결과 계산 (전체 개수 - 기준 점수 이상이 시작되는 인덱스)
int count = list.size() - left;
answer[i++] = count;
}
return answer;
}
// 16가지 쿼리 조합을 만들어 map에 <Key, Point>를 저장하는 재귀 함수
private void recursion(int idx, String str, String[] data, int point){
// 4가지 스펙 조합이 완성되면
if(idx == 4){
// map에 key가 없으면 새 ArrayList 생성, 있으면 기존 리스트 반환
List<Integer> list = map.computeIfAbsent(str,k->new ArrayList<Integer>());
list.add(point); // 점수 추가
return;
}
// idx번째 스펙을 와일드카드(-)로 처리
recursion(idx + 1,str + "-",data,point);
// idx번째 스펙을 실제 값으로 처리
recursion(idx + 1,str + data[idx],data,point);
}
}5. 회고
- 시간 복잡도 먼저 고려하지 않아서 첫 시도가 실패했기때문에 문제를 좀 더 꼼꼼히 봐야겠다는 필요성을 느낌.
- 데이터의 크기와 제한 시간을 보고 효율적인 자료구조와 알고리즘을 조합하는 능력이 필요한 문제
- 핵심 자료구조 : HashMap
- 핵심 알고리즘: 재귀, 이진 탐색
왜? 라는 질문이 사라질 때까지