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

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

프로그래머스

2021 KAKAO BLIND RECRUITMENT Level 2 문제다.

 

 

info의 각 값들을 2차원 배열에 넣고, query를 탐색하며 info를 하나하나 비교하는 코드를 작성했다.

정확성은 맞는데 효율성 테스트를 틀려서 문제 조건을 다시 보니,

info 크기는 최대 50000이고 query 크기는 최대 100000이기 때문에 시간 초과가 날 수 밖에 없었다.

 

 

https://coding-grandpa.tistory.com/104

[2021 카카오 코딩테스트] 순위 검색 - 자바 java

도저히 생각이 나질 않아서 이 분의 유튜브 설명을 참고했다. 

문제에 대한 설명만 듣고 코드는 직접 짜봤는데 거의 비슷한 것 같다.

 

먼저 map의 key에 info의 각 값들이 통과할 수 있는 조건을 모두 조합해 넣고, value에는 코딩테스트 점수를 넣는다.

예를 들어 java backend junior pizza 150 이라면

query의 조건으로 들어왔을 때 통과할 수 있는 문자열은 아래와 같다.

 

javabackendjuniorpizza

-backendjuniorpizza

java-juniorpizza

javabackend-pizza

javabackendjunior-

--juniorpizza

-backend-pizza

(...)

----

 

이 모든 문자열을 map의 key로 넣고, 코딩테스트의 점수 150을 value로 넣는다.

 

그리고 java backend junior chicken 80은

위의 문자열 조합과 중복된 javabackendjunior- 이라는 조건을 통과할 수 있으므로

javabackendjunior-을 key로 가졌을 때의 value는  [150, 80]이 된다.

 

즉, map에는 query의 조건의 조합, key에는 그 조건을 만족하는 코딩테스트의 List가 저장된다.

코딩테스트 점수를 기준으로 이분탐색을 해야하므로 

map의 List를 정렬한 후, 이분 탐색을 해준다.

 

List가 70 80 150 150 160 170이고 query의 코딩테스트 점수가 150이라면

List에서 150 이상인 원소가 처음으로 나타나는 지점을 찾고,

List의 전체 size에서 그 지점을 빼면 구하려는 값이 된다.

이는 원소의 하한선이므로 이를 고려해서 이분탐색을 구현한다.

 

 

 

- 배운점 / 느낀점

카카오 Level 2는 대부분 구글링 없이 풀 수 있었는데 이번엔 그러지 못했다. 내기준 Level 3인 것 같다..ㅠㅠ

정렬된 배열에서 특정 값을 찾을 때에는 이분 탐색을 사용할 수 있는데,

이런 문제가 나오면 이분 탐색을 생각하지 못하고 무조건 완탐으로 풀어보는 것 같다.

풀기 전에 주어지는 값들의 최대값을 꼭 고려하고 알고리즘을 선택해야겠다.

그리고 하나하나 비교하는 것보다 모든 경우를 조합한 후 map에 넣어서 비교하는 방법이 더 효율적이라는 것....

다음엔 꼭 활용해야지. + 이분탐색 연습 더 하기!

 

import java.util.*;

class Solution {    
    static HashMap<String, ArrayList<Integer>> map = new HashMap<>();

    public int[] solution(String[] info, String[] query) {
        for(int i=0;i<info.length;i++) 
            DFS(info[i].split(" "), "", 0);

        int n = query.length;
        int result[] = new int[n];

        // 코딩 테스트 점수를 기준으로 오름차순 정렬
        for(ArrayList<Integer> list : map.values()) 
            Collections.sort(list);

        for(int i=0;i<n;i++)
            result[i] = BinarySearch(query[i]);

        return result;
    }

    // 가능한 모든 문자열 조합하기 (key: 문자열 / value: 코딩 테스트 점수)
    static void DFS(String[] info, String str, int depth) {
        if(depth == 4) {
            int score = Integer.parseInt(info[depth]);
            if(map.containsKey(str)) {
                map.get(str).add(score);
            }
            else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(score);
                map.put(str, list);
            }
            return;
        }

        DFS(info, str + "-", depth + 1);
        DFS(info, str + info[depth], depth + 1);
    }

    // 코딩 테스트 점수를 이분 탐색하여 조건을 만족하는 인원 수 찾기
    static int BinarySearch(String query) {
        String[] arr = query.split(" and ");
        int score = Integer.parseInt(arr[3].split(" ")[1]);

        query = arr[0] + arr[1] + arr[2] + arr[3].split(" ")[0];

        if(!map.containsKey(query))
            return 0;

        ArrayList<Integer> list = map.get(query);
        int start = 0;
        int end = list.size();

        // score 이상인 값이 처음으로 나타나는 인덱스 찾기(하한선)
        while(start < end) { 
            int mid = (start + end) / 2;

            if(list.get(mid) >= score)
                end = mid;
            else // list.get(mid) > score
                start = mid + 1;
        }

        return list.size() - start;
    }
}