[프로그래머스/Level2] 순위 검색(JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• DFS + 이분 탐색

필요 자료구조
- (문자열, 점수 저장하는 리스트) 저장하는 HashMap

 

- DFS로 info가 포함될 수 있는 모든 경우의 수를 HashMap으로 만들어 map에 key로 넣고 점수를 value의 리스트의 값으로 넣어준다.

- query를 key로 하는 value들을 가져와 이분 탐색한다. → 그래야 시간초과가 안 난다고 함

 

HashMap을 사용하는 이유

: 한 번에 바로 탐색하기 위해

 

 

💥 유의사항

- 시간 초과 주의

- 이분 탐색 전 HashMap의 value인 리스트는 오름차순 정렬해두기!

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static HashMap<String, List<Integer>> map = new HashMap<>();    // info가 포함될 수 있는 경우의 수 , 점수
    
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        
        // 1. info에 있는 값을 띄어쓰기 기준으로 분리하고, 만들 수 있는 모든 경우의 수 만들기
        for(int i = 0 ; i < info.length ; i++) {
            String[] s = info[i].split(" ");
            makeSentence(s, 0, "");
        }
        
        // 2. map의 value인 점수 리스트들 오름차순 정렬하기 (이분탐색 위해)
        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(" ");
            
            // q[0]으로 map 조회하고, 리스트에 해당하는 값들 가져오기
            if(map.containsKey(q[0]))
                answer[i] = binarySearch(q[0], Integer.parseInt(q[1])); 
            else
                answer[i] = 0;
        }        
        
        return answer;
    }
    
    // [DFS] 각 항목이 속할 수 있는 모든 경우의 수 구해 map에 점수 넣기
    private static void makeSentence(String[] strArr, int cnt, String str) {
        if(cnt == 4) {
            if(!map.containsKey(str)) {
                List<Integer> list = new ArrayList<>();
                map.put(str, list); 
            }
            
            map.get(str).add(Integer.parseInt(strArr[4]));  // map의 value인 리스트에 점수 넣기
            return;
        }
        
        makeSentence(strArr, cnt + 1, str + "-");           // - 포함한 조합
        makeSentence(strArr, cnt + 1, str + strArr[cnt]);   // - 제외한 조합
    }
    
    // [이분 탐색] key로 map을 조회해 score 이상 받은 사람 수 계산하기
    private static int binarySearch(String key, int score) {
        List<Integer> list = map.get(key);
        
        int start = 0;
        int end = list.size() - 1;
        
        while(start <= end) { // score 이상인 값이 처음으로 나타나는 인덱스 찾기 (하한선)
            int mid = (start + end) / 2;
            
            if(list.get(mid) < score)
                start = mid + 1;
            else
                end = mid - 1;
        }
        
        return list.size() - start; // key에 해당하는 점수의 총 개수 - 최소 점수보다 크거나 같은 처음 idx
    }
}

 

 

 

---

💦 어려웠던 점

- 데이터 크기 보고 완탐하면 백퍼 시간초과 걸릴텐데 싶었는데 역시나 그 부분에서 HashMap을 썼다.

- '-'가 섞여있는 경우를 DFS로 만들어 사용할 생각을 하지 못 했다.

- 띄어쓰기를 어떻게 처리해서 값을 활용할지 고민이 되었다,,

 

🧐 새로 알게 된 내용

- 이분 탐색할 아이디어

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[level2] 프로그래머스 - 순위 검색(JAVA)

 

[JAVA] 프로그래머스 - 순위 검색

 

[프로그래머스/자바] 순위 검색 풀이 - 2021 KAKAO BLIND RECRUITMENT