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

 

 

레벨2에.. 효율성이라니요!!!!
개인적으로는 지금까지 차례대로 푼
1~2단계 문제중엔 제일 어려웠다..
방법을 몰라서..ㅎ

 

 

[ 문제 해석 ]

- 이 문제는 시간초과가 있으므로, info와 query를 하나씩 비교하면 시간초과가 난다ㅠㅠ

- info가 포함될 수 있는 모든 경우의 수를 map에 key로 넣고 점수를 value로 넣어준다.

- query를 key로하는 value들을 가져와서 이분탐색한다!! 
   => 그래야 시간초과가 안 난다.ㅠㅠ

 

 

 

 

[ 풀이 방법 ]

1. info에 있는 값을 다음과 같이 바꿔준다.

{ "언어", "직군", "경력", "소울푸드",  "점수" }

ex) "java backend junior pizza 150"

 

 

2. "언어", "직군", "경력", "소울푸드" 가 속할 수 있는 모든 경우의 수를 구해 map에 점수를 넣어준다.

ex) [ "java", "backend", "junior", "pizza", "150" ]는 아래의 경우에 모두 해당되므로, 점수를 넣어준다.

 

 

3. info에 대해 처리를 완료하면, 다음과 같다.

 

 

4. map의 value인 점수 List들을 오름차순으로 정렬한다.

for (String key : map.keySet())
	Collections.sort(map.get(key));

 

 

5. query의 각 문장을 다음과 같이 만들어준다.

[ "javabackendjuniorpizza", "100" ]

ex)

query[i] = query[i].replaceAll(" and ", "");
String[] q = query[i].split(" ");

 

 

6. 4번에서 구한 q[0]로 map을 조회하여, List(해당하는 값)들을 가져온다.

    List를 이분탐색하여, 점수(q[1]) 이상 받은 사람 수를 구한다.    

    // 이분 탐색
    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;
        }
 
	// key에 해당하는 점수의 총 개수 - 점수보다 크거나 같은 처음 index
        return list.size() - start;
    }

 

 

 

 

[ 전체 코드 ]

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);
    }
}

 

 

질문이나 이상한점은 댓글 부탁드려욥 :)