[Java/프로그래머스] 순위검색 (시간초과 해결)

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

코딩테스트 연습 - 순위 검색

문제 설명은 위 링크를 참조하면 된다.

 

처음에는 모든 id, 언어, 경력, 직군, 소울푸드, 점수 6가지 변수를 가지고 있는 클래스를 만들어서 

info 배열을 이용해서 각각의 java python cpp backend frontend.... 이런 것들을 다 Key로 사용하고 6가지 변수 가지고 있는 클래스 객체의 Set을 Value로 써서 저장한다. 

그리고 query에서 매번 retainAll 해서 정답 후보 Set을 구하고 

Set의 원소들을 확인하며 기준 점수 이상인 경우에만 카운트해서 답을 구해주었다. 

그런데 이렇게 하면 O(NM)으로 5만(N) 10만(M) 5,000,000,000의 연산이 된다. 따라서 시간초과가 날 수밖에 없는 것이다.

(다음부터는 시간복잡도를 신경써서 방향을 정하고 풀어서 시간 낭비하는 일이 없도록 해야겠다..)

 

한참을 고민하다가 결국 유튜브에 검색해서 실마리를 얻었다.

https://www.youtube.com/watch?v=eBQtFteduyw 

저분 정말 설명을 쉽게 잘해주신다.

시간초과 안나게 풀이하는 방법을 요약하면 다음과 같다.

먼저 모든 경우의 수는 4 * 3 * 3 * 3 = 108가지이다.

우리가 문제를 풀기 위해서 필요한 것은 결국 앞 4개의 문자열 쿼리에 맞는 점수들 뿐이다.

그리고 검색 효율을 위해 정렬된 점수들이 필요하다.

그러므로 108가지 각각의 쿼리에 해당하는 점수 리스트를 미리 만들어놓으면 될 것이다. 

그리고 다 만들면 정렬해서 이진탐색을 통해 인덱스를 구하고 그 인덱스를 이용해서 답을 내면

O(M*logN) 이므로 10만*log5만 이라고 해도 크지 않음을 알 수 있다. (정렬은 NlogN으로 무시)

강의 앞부분만 보고 신나서 코딩하러 달려가서 강의에 나온 내용과 마지막 답 내는 부분이 좀 다르다.

1. 강의에서 알려준 방법중 4차원과 1차원이 있는데 4차원이 편할 것 같아서 4차원 했는데 생각보다 안편하더라

2. 강의는 16가지 넣어주는 부분을 for문으로 해결했지만 그거 어떤 원리인지  이해가 아직 잘 안돼서 일단 나는 그냥 16줄 써봤다..ㅎㅎ 

3. 그리고 답을 좀 편하게 내고 싶어서(근데 막상 편하진 않았던..) 내림차순 정렬하고 binarySearch+linearSearch조합으로 들어가야할 자리 찾으면 그거 반환해서 바로 정답배열에 넣어주었다. (Collections.binarySearch를 몰랐다.)

 

맨 위 주석 주저리주저리 써놨는데 그냥 코드와 코드 근처 주석만 보면 한참 뒤에 보아도 쉽게 이해될 것이다. 

/*
 * 언어 선택, 백 프론트 선택, 주니어 시니어 선택, 치킨 피자 선택
 * 정보는 5만 쿼리는 10만
 * 쿼리각각을 매번 정보확인에 쓴다면??  500000만으로 숫자가 너무 큼
 * 따라서 모든 경우의 수의 숫자를 미리 구해놓으면 된다. 
 * 4 * 3 * 3 * 3 = 108가지 근데 또 점수가 문제네..
 * 그럼 클래스를 만들고 Map<String, Set<Candidate>>을 각 선택별로 만들어서 저장하는 것은 어떤가?? 
 * 그럼 하나의 쿼리요소마다 교집합하면 답이 나온다. retainAll의 시간복잡도는??
 * 아마도 O(N)일 확률이 높다. 
 * 이거 만드는데 20만 밖에 안든다. 그리고 교집합 연산 4번으로 답을 구할 수 있다.
 * 시간초과가 났는데 NlogN으로 미리 각각 정렬하고 교집합 하고
 * logN으로 기준점수 찾고 전체인덱스 - 기준인덱스 + 1 하면 더 빨리 구할 수 있다.
 * --- 이하는 강의를 보고 생각과 코드를 바꾼 내용이다. ---
 * 나는 문제에서 원하는 결과만 내주면 된다.
 * 문제에서 원하는 결과는 점수 이전까지의 쿼리에 맞는 참가자들을 알고 
 * 그중에서 해당 점수 이상의 참가자들이 몇명인지만 알면된다.
 * 즉 점수와 몇명인지만 알면 된다는 것.
 * 즉 점수 리스트만 있고 정렬되어있다면 logN으로 몇명인지 찾을 수 있다. 
 * 문제에서 쿼리가 info는 5만밖에 안되고 query가 10만이나 됐을 때부터 눈치를 챘어야했다.
 * 108가지 미리 구해놔야한다는 것까지는 생각이 닿았는데 어떻게 구현할지 막막했다.
 * 강의에 나온 방식으로 ArrayList<Integer>의 4차원배열 만들고 HashMap<쿼리요소, 인덱스>로 인덱스를 찾아서
 * 해당 ArrayList에는 점수만 넣어주면된다!!!
 * 결국 다시 말하지만 문제에서 원하는 정답을 내려면 핵심적으로 필요한 게 무엇인지 생각해보고 
 * 그것만 구하면 된다는 마인드로 문제풀이의 실마리를 잡아야한다. 그 이외의 정보는 불필요하다.
 * if()문 뒤에 ;찍지마... 없는 취급된다구..
 * 아 생각해보니 query개수랑 정답 개수랑 같네.. index query랑 같이 돌면서 그대로 넣어줘도 되겠다.
 */
import java.util.*;
class Solution {
    public int[] solution(String[] info, String[] query) {
        //108가지 조합마다 점수리스트를 만들기 위한 초기화
        HashMap<String, Integer> idxMap = new HashMap<>(); // String을 보고 Index를 찾기위해 Map을 사용
        ArrayList<Integer>[][][][] scores = new ArrayList[4][3][3][3];
        idxMap.put("-", 0); //공통
        
        idxMap.put("java", 1); // 언어
        idxMap.put("cpp", 2);
        idxMap.put("python", 3);
        
        idxMap.put("backend", 1); // 직군
        idxMap.put("frontend", 2);
        
        idxMap.put("junior", 1); // 경력 
        idxMap.put("senior", 2);
        
        idxMap.put("chicken", 1); // 소울푸드
        idxMap.put("pizza", 2);
        
        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 3; j++) {
                for(int k = 0; k < 3; k++) {
                    for(int l = 0; l < 3; l++) {
                        scores[i][j][k][l] = new ArrayList<Integer>();
                    }
                }
            }
        }
        
        // 주어진 info 입력에 따라 108가지 점수리스트 만들기
        for(String i : info) {
            String[] one = i.split(" ");
            int lang = idxMap.get(one[0]);
            int duty = idxMap.get(one[1]);
            int career = idxMap.get(one[2]);
            int food = idxMap.get(one[3]);
            int score = Integer.parseInt(one[4]);
           
            scores[lang][duty][career][food].add(score);
            scores[0][0][0][0].add(score);
            
            scores[0][duty][career][food].add(score);
            scores[lang][0][career][food].add(score);
            scores[lang][duty][0][food].add(score);
            scores[lang][duty][career][0].add(score);
            
            scores[0][0][career][food].add(score);
            scores[0][duty][0][food].add(score);
            scores[0][duty][career][0].add(score);
            scores[lang][0][0][food].add(score);
            scores[lang][0][career][0].add(score);
            scores[lang][duty][0][0].add(score);
            
            scores[0][0][0][food].add(score);
            scores[0][0][career][0].add(score);
            scores[0][duty][0][0].add(score);
            scores[lang][0][0][0].add(score);
        }
        
        // 이분탐색을 위한 정렬 
        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 3; j++) {
                for(int k = 0; k < 3; k++) {
                    for(int l = 0; l < 3; l++) {
                        Collections.sort(scores[i][j][k][l], Collections.reverseOrder());
                    }
                }
            }
        }
        
        int[] answer = new int[query.length];
        for(int i = 0; i < query.length; i++) {
            String[] one = query[i].split(" ");
            // 0 2 4 6(인덱스 쿼리) + 7(점수)
            int lang = idxMap.get(one[0]);
            int duty = idxMap.get(one[2]);
            int career = idxMap.get(one[4]);
            int food = idxMap.get(one[6]);
            //System.out.println(one[0] +" "+ one[2]+" "+one[4]+" "+one[6]+" "+one[7]);
            int score = Integer.parseInt(one[7]);
            ArrayList<Integer> list = scores[lang][duty][career][food];
            int len = list.size();
            if(len > 0 && list.get(0) >= score)
                answer[i] = binarySearch(list, score, 0, len-1);
            else //길이가 0이거나 오름차순이니 첫번째 숫자가 가장큰데 그게 기준점수보다 작다면 답은 0이다.
                answer[i] = 0;
        }
        
      
        return answer;
    }
    /*
     * 이분탐색 함수
     * 일반적인 이분탐색과는 다른 점이, 딱 찾는 게 아니라 기준 점수보다 큰 최소점수를 찾아야한다.
     * 범위가 일정 길이 이하가 되면 liear search로 찾아준다.
     * @param : ArrayList<Integer> 쿼리에 해당하는 점수들이 담긴 리스트 (내림차순임에 주의)
     * @param : score 기준점수
     * @return : 그대로 정답에 들어갈 인덱스 값
     */
    static int binarySearch(ArrayList<Integer> list, int score, int left, int right) {
        if(right - left < 5) {
            for(int i = left; i <= right; i++) {
                if(list.get(i) < score)
                    return i;
            }
            return right+1;
        }
        int mid  = (left + right) / 2;
        if(list.get(mid) < score) {
            return binarySearch(list, score, left, mid-1);
        }
        else 
            return binarySearch(list, score, mid+1, right);
    }
}

<추가>

Collections.binarySearch의 존재를 이번에 처음 알게되었다.

오름차순으로 정렬된 경우만 사용가능하다고 한다.

대상을 찾았을 때는 그대로 그 인덱스를 반환하지만, 

찾지 못한다면 ((- 리스트에 대상이 존재했다면 위치하는 인덱스) -1)을 리턴한다고 한다.

예를들어 4 6 7 9 26 이렇게 있는 배열에서 Collections.binarySearch로 8을 찾는다면 (-3)-1 = -4를 반환하는 것이다.