순위 검색(Lv.2)

 

---

 

문제 설명

 

 

 

입출력 예시

 

 

요약

query에 해당하는 지원자의 수를 담은 int 배열 return

 

---

 

풀이

 

문제 해석

query[i] 를 만족하는 지원자들을 info에서 찾기

 

 

접근 방식

1) info에 있는 지원자 정보를 가지고 모든 경우의 수를 가진 map 구성

  → 카테고리: 4개, 선택사항: 2개 이므로 경우의 수는 총 16가지

 

2) 동일한 조건을 가진 지원자가 존재할 수 있으므로 value는 점수를 담은 ArrayList로 생성

  → sort를 통한 오름차순 정렬

 

3) query[i]가 map의 key로 존재한다면 해당 조건을 만족하는 지원자의 수 구하기

  → 효율성 검사를 통과하기 위해서 이분 탐색을 활용

 

 

실행 결과

info의 각 요소에 대한 모든 경우의 수를 포함한 map

 

---

 

코드 리뷰

 

import java.util.*;

class Solution {
    public int[] solution(String[] info, String[] query) {
        HashMap<String, List<Integer>> map = new HashMap<>();
        List<Integer> answerList = new ArrayList<>();
        for(int i = 0; i < info.length; i++) {
            String[] data = info[i].split(" ");
            String[] languages = {data[0], "-"};	// 각 카테고리는 '상관없음'을 뜻하는 "-"를 항목으로 가질 수 있다.
            String[] jobs = {data[1], "-"};
            String[] careers = {data[2], "-"};
            String[] foods = {data[3], "-"};
            int score = Integer.valueOf(data[4]);
            for(String language : languages) {		// 각 카테고리에서 '상관없음'을 포함한 모든 경우의 수를 map에 담는다.
                for(String job : jobs) {
                    for(String career : careers) {
                        for(String food : foods) {
                            String key = String.join(" ", language, job, career, food);
                            List<Integer> list = map.getOrDefault(key, new ArrayList<>());
                            list.add(score);	// 동일한 조건의 지원자가 있을 수 있으므로 list에 점수를 추가해서 다시 map에 담는다.
                            map.put(key, list);
                        }
                    }
                }
            }
        }
        for(String key : map.keySet()) {	// 탐색을 위한 오름차순 정렬
            List<Integer> list = map.get(key);
            Collections.sort(list);
            map.put(key, list);
        }
        int[] answer = new int[query.length];
        for(int i = 0; i < query.length; i++) {
            String[] data = query[i].split(" and ");
            String key = String.join(" ", data[0], data[1], data[2], data[3].split(" ")[0]);	// 조건
            int score = Integer.valueOf(data[3].split(" ")[1]);	// 타겟 점수
            if(map.containsKey(key)) {		// 해당 조건과 동일한 조건을 가진 지원자가 있다면
                List<Integer> list = map.get(key);
                int left = 0;
                int right = list.size();
                while(left < right) {	// 이분 탐색 시작(left == right 시점에 종료)
                int mid = (left + right) / 2;
                if(list.get(mid) >= score) {	// 타겟이 중간에 위치한 값보다 왼쪽에 위치한다면
                    right = mid;		// mid 기준 오른쪽 부분(size의 절반) 제외
                    } else {			// 타겟이 중간에 위치한 값보다 오른쪽에 위치한다면
                    left = mid + 1;		// mid 기준 왼쪽 부분(size의 절반) 제외
                    }
                }
                answer[i] = list.size() - left;	// 타겟 점수보다 작은 부분 제거
            }
        }
        return answer;
    }
}

 

 

 

* refs

https://www.youtube.com/watch?v=vFwVvJQnC4M&list=PLlV7zJmoG4XI9VguUVNMu3pCjssb4aR_0&index=9