[프로그래머스] Level 2 : 순위 검색(Java)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/72412

프로그래머스

---

💡 풀이

주어진 info 값과 query문을 하나씩 비교해서 풀었더니, 효율성 검사에서 통과하지 못했습니다. 시간초과가 발생한 것이죠.

따라서, info를 탐색해 매 info마다 가능한(포함될 수 있는) 모든 경우의 수를 map의 key로 넣고, value에는 점수를 넣어 query에서 탐색하는 방법을 이용합니다. 이때, query에서 제시한 점수 이상인 info들의 값을 구하기 때문에 이분 탐색을 이용합니다. 

info 값 바꾸기

java backend junior pizza 150

위처럼 주어진 info의 값을 점수를 제외하고 공백이 없도록 아래와 같은 형태로 바꿔줍니다. 

javabackendjuniorpizza 150

여기서 앞의 문장은 Key, 뒤의 점수는 Value가 됩니다. 

for(int index = 0; index < info.length; index++) {
        String[] information = info[index].split(" ");
        makeQuery(information, "", 0);
    }
    
...

 void makeQuery(String[] information, String str, int depth) {
    if(depth == 4) {
        if(!allPossibleMap.containsKey(str)) {
            List<Integer> list = new ArrayList<>();
            allPossibleMap.put(str, list);
        }
        allPossibleMap.get(str).add(Integer.parseInt(information[depth]));

        return;
    }

    makeQuery(information, str + "-", depth + 1);
    makeQuery(information, str + information[depth], depth + 1);
}

이때, 재귀를 사용해 앞 단어부터 자신과 "-"를 반복하며 붙여 나갑니다. 그럼 Map에는 (" javabackendjuniorpizza", [150])와 같은 형태로 들어갈 것입니다. 

 

그리고, 이 Map을 value인 점수 List를 오름차순으로 정렬해 줍니다. 

for(String key : allPossibleMap.keySet()) {
    Collections.sort(allPossibleMap.get(key));
}

 

query 값 바꾸기

Map의 key값과 같은 형태로 만들기 위해 주어진 모든 query들도 info와 같은 형태로 변경해줍니다.

query[index] = query[index].replaceAll(" and ", "");
String[] oneQuery = query[index].split(" ");

이때, oneQuery의 0번 index는 문자열, 1번 index는 점수가 될 것입니다. 

 

이분 탐색

query에서 제시한 점수 이상을 선택하길 원하기 때문에, 이분 탐색을 이용합니다. 이미 info의 value 값을 오름차순으로 정렬해두었기 때문에 이분 탐색을 이용할 수 있습니다. 

 int binarySearch(String key, int score) {
    List<Integer> list = allPossibleMap.get(key);

    int start = 0;
    int end = list.size() - 1;

    while(start <= end) {
        int mid = (start + end) / 2;

        if(list.get(mid) < score){
            start = mid + 1;
            continue;
        }
        end = mid - 1;
    }

    return list.size() - start;
}

list.size() -start는 $(key에 해당하는 점수의 총 개수) - (점수보다 크거나 같은 값의 시작 index)$이기 때문에 해당 점수 이상의 값의 개수를 구할 수 있습니다. 

 

전체 코드

전첵적인 코드는 다음과 같습니다. 

import java.util.*;

class Solution {
    Map<String, List<Integer>> allPossibleMap = new HashMap<>();
    
    public int[] solution(String[] info, String[] query) {
        for(int index = 0; index < info.length; index++) {
            String[] information = info[index].split(" ");
            makeQuery(information, "", 0);
        }
        
        for(String key : allPossibleMap.keySet()) {
            Collections.sort(allPossibleMap.get(key));
        }
        
        int[] answer = replaceQuery(query);
        return answer;
    }
    
    void makeQuery(String[] information, String str, int depth) {
        if(depth == 4) {
            if(!allPossibleMap.containsKey(str)) {
                List<Integer> list = new ArrayList<>();
                allPossibleMap.put(str, list);
            }
            allPossibleMap.get(str).add(Integer.parseInt(information[depth]));
            
            return;
        }
        
        makeQuery(information, str + "-", depth + 1);
        makeQuery(information, str + information[depth], depth + 1);
    }
    
    int[] replaceQuery(String[] query) {
        int[] result = new int[query.length];
        
        for(int index = 0; index < query.length; index++) {
            query[index] = query[index].replaceAll(" and ", "");
            String[] oneQuery = query[index].split(" ");
            
            if(allPossibleMap.containsKey(oneQuery[0])) {
                result[index] = binarySearch(oneQuery[0], Integer.parseInt(oneQuery[1]));
                continue;
            }
            result[index] = 0;
        }
        
        return result;
    }
   
    int binarySearch(String key, int score) {
        List<Integer> list = allPossibleMap.get(key);
        
        int start = 0;
        int end = list.size() - 1;
        
        while(start <= end) {
            int mid = (start + end) / 2;
            
            if(list.get(mid) < score){
                start = mid + 1;
                continue;
            }
            end = mid - 1;
        }
        
        return list.size() - start;
    }
}