[프로그래머스] 카카오_순위 검색 (자바 풀이)

문제

https://programmers.co.kr/learn/courses/30/lessons/72412?language=java 

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

 

풀이

이 문제는 문자열 처리와 이분 탐색을 이용한 효율적인 탐색을 잘해야 한다. 나는 ArrayList 배열 db[][][][]를 만들어 점수를 저장하였다. 예를 들어 "python" = 2, "backend" = 0, "senior" = 1, "chicken"=0으로 변환해서, 

db[2][0][1][0].add(150) 이런 식으로 점수를 저장하였다. 문자열을 정수로 변환하는 것은 HashMap을 이용했다.

 

이렇게 저장한 점수를 이분탐색을 통해서 조회하기만 하면 된다. 하지만 까다로운 점이 하나 있었다. "-"는 모든 경우의 수를 다 살펴봐야 하므로 예외 처리를 해주어야 한다. 나는 이것을 반복문의 index 처리를 하여 해결하였다.

 

예를 들어, 가장 앞의 언어 선택이 "-"라면, 0부터 2까지 전부 살펴보도록 인덱스를 설정하고, "java"와 같이 딱 정해져 있는 경우는 2부터 2까지만, 즉 해당 부분만 조회하도록 설정하였다.

 

사실 말로 쓰는 풀이보단, 코드를 보는게 더 이해가 빠를 것이다.

 

코드

 

import java.util.*;
 
class Solution {
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        ArrayList<Integer> db[][][][] = new ArrayList[3][2][2][2];
        HashMap<String,Integer> dict = new HashMap<>();
        dict.put("cpp", 0); dict.put("java", 1); dict.put("python", 2);
        dict.put("backend", 0); dict.put("frontend", 1);
        dict.put("junior", 0); dict.put("senior", 1);
        dict.put("chicken", 0); dict.put("pizza", 1);
        for(int i=0; i<3; i++){
            for(int j=0; j<2; j++){
                for(int k=0; k<2; k++){
                    for(int l=0; l<2; l++){
                        db[i][j][k][l] = new ArrayList<Integer>();
                    }
                }
            }
        }
        
        for(int i=0; i<info.length; i++){
            String temp[] = info[i].split(" ");
            db[dict.get(temp[0])][dict.get(temp[1])][dict.get(temp[2])][dict.get(temp[3])].add(Integer.parseInt(temp[4]));
        }
        for(int i=0; i<3; i++){
            for(int j=0; j<2; j++){
                for(int k=0; k<2; k++){
                    for(int l=0; l<2; l++){
                        Collections.sort(db[i][j][k][l]);
                    }
                }
            }
        }
        
        for(int idx=0; idx<query.length ; idx++){
            String temp[] = query[idx].split(" and ");
            String temp2[] = temp[3].split(" ");
            
            int is,ie,js,je,ks,ke,ls,le;
            if(temp[0].equals("-")){
                is=0; ie=2;
            }else{
                is = ie = dict.get(temp[0]);
            }
            
            if(temp[1].equals("-")){
                js=0; je=1;
            }else{
                js = je = dict.get(temp[1]);
            }
            
            if(temp[2].equals("-")){
                ks=0; ke=1;
            }else{
                ks = ke = dict.get(temp[2]);
            }
            
            if(temp2[0].equals("-")){
                ls=0; le=1;
            }else{
                ls=le=dict.get(temp2[0]);
            }
            
            int cnt = 0;
            for(int i=is; i<=ie; i++){
                for(int j=js; j<=je; j++){
                    for(int k=ks; k<=ke; k++){
                        for(int l=ls; l<=le; l++){
                            cnt += binarySearch(db[i][j][k][l], Integer.parseInt(temp2[1]));
                        }
                    }
                }
            }
            
            answer[idx] = cnt;
            
        }
                                
        return answer;
    }
    
    public static int binarySearch(ArrayList<Integer> db, int score){
        int left = 0;
        int right = db.size();
        int mid;
        
        while(left<right){
            mid = (left+right)/2;
            
            if(db.get(mid) >= score){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        
        return db.size()-right;
        
    }
}