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

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

프로그래머스

코딩테스트 연습 > 2021 KAKAO BLIND RECRUITMENT > 순위 검색

 

시간 초과 코드 (정확성 100점 / 효율성 0점)

import java.util.*;
import java.util.stream.*;
class Solution {
    static class Applicant {
        private String lang;    // cpp, java, python
        private String job;     // backend, frotend
        private String career;  // senior, junior
        private String soulFood;// pizza, chicken
        private int score;   // 코테 점수
        public Applicant(String input){
           String [] splits = input.split(" ");
            
           this.lang = splits[0];
           this.job = splits[1];
           this.career = splits[2]; 
           this.soulFood = splits[3];
           this.score = Integer.parseInt(splits[4]); 
        }
        
        public String toString(){
            return this.lang + " " + this.job + " " + this.career + " " + this.soulFood + " " + 
                              this.score;
        }
    }
  
    public int[] solution(String[] info, String[] query) {
        
        ArrayList<Applicant> list = new ArrayList<>();
        
        for(int i = 0; i < info.length; i++){
            list.add(new Applicant(info[i]));
        }
        
        int[] answer = new int [query.length];
        for(int i = 0; i < query.length; i++){
            String cur = query[i];
            String [] filter  = query[i].split(" and ");
            String [] filter2 = filter[3].split(" ");
            // 언어: filter[0] 직군: filter[1] 경력: filter[2]
            // 소울푸드: filter2[0] 점수: filter2[1]
            long count = list.stream().filter(o -> {
                if(!filter[0].equals("-") && !o.lang.equals(filter[0])){
                    return false;
                }
                if(!filter[1].equals("-") && !o.job.equals(filter[1])){
                    return false;
                }
                if(!filter[2].equals("-") && !o.career.equals(filter[2])){
                    return false;
                }
                if(!filter2[0].equals("-") && !o.soulFood.equals(filter2[0])){
                    return false;
                }
                if(!filter2[1].equals("-") && o.score < Integer.parseInt(filter2[1])){
                    return false;
                }
                return true;
            }).count();
            
            answer[i] = (int)count;
        }
        
        return answer;
    }
}

 

처음에는 지원자들의 정보를 Applicant 클래스로 정리를 하고 stream 연산을 통해서 정답을 구했는데

역시나 시간 초과가 발생하였다. 

문제 접근

나는 이분탐색과 map 자료구조 그리고 백트래킹을 활용했다. 

 

java backend junior pizza 100

이 5가지 값중에 점수를 빼고 java - backend - junior - pizze 이렇게 4가지로 key를 만든다. 

ex)

java:0 cpp:1 python2 / backend:0 frontend:1

 

java - backend 

 

key: 01 이런식으로 

 

그렇게 key를 만들고 map 자료구조에 저장 map 자료구조는

HashMap<String, ArrayList<Integer>> record = new HashMap<>(); 이렇게 코테 점수를 보관하도록 만든다. 

 

그리고 쿼리 또한 key 형태로 바꾸고("-"를 고려해서 백트래킹을 사용) map에서 꺼내서 해당 점수보다 높은 인원들을 

이분 탐색으로 구하면 된다. 

 

init() 메서드 

 public static void init(){
    map.put("java", "0");
    map.put("cpp", "1");
    map.put("python", "2");
    map.put("backend", "0");
    map.put("frontend", "1");
    map.put("junior", "0");
    map.put("senior", "1");
    map.put("chicken", "0");
    map.put("pizza", "1");
}

해당 메서드는 단순하게 map을 초기화한다. map은 String key, String value를 가진다. 

나중에 record map의 key를 만들 때나 쿼리를 통해서 key를 만들 때 사용되는 map이다 

 

func1(info) 메서드 

public static void func1(String[] info){
    for(String temp : info){
        String [] split = temp.split(" ");
        String key = "";
        for(int i = 0 ; i < 4; i++){
            key += map.get(split[i]);
        }
        if(!record.containsKey(key)){
            ArrayList<Integer> list = new ArrayList<>();
            list.add(Integer.parseInt(split[4]));
            record.put(key, list);
        }
        else record.get(key).add(Integer.parseInt(split[4]));
    }
}

func1() 메서드는 지원자 정보를 split 으로 파싱하고 값들을 key로 변환한 이후 record 이름의 map에 점수를 저장한다. 

 

func2() 메서드 

public static void func2(){  // 정렬 
    Set<String> set = record.keySet();
    for(String key : set){
        Collections.sort(record.get(key));
    }
}

func2() 메서드는 앞으로의 이분 탐색을 위해서 미리 모든 리스트를 정렬하는 메서드이다. 

 

 

func3() & func3() 호출하는 for문 

for(int i=0; i < query.length; i++){ 
    sum = 0;
    split1 = query[i].split(" and ");
    split2 = split1[3].split(" ");
    split1[3] = split2[0]; 
    func3(0, ""); // 백트래킹을 활용해서 여러가지 경우의 쿼리 만들기 
    answer[i] = sum; // 정답 기록 
}

public static void func3(int depth, String key){
    if(depth == 4){
        if(!record.containsKey(key)) return;

        ArrayList<Integer> temp = record.get(key);
        // 이분 탐색 시작 

        int start  = 0;
        int end    = temp.size();
        int target = Integer.parseInt(split2[1]);

        while(start < end){
            int mid = (start + end) / 2;
            if(temp.get(mid) >= target){
                end = mid;
            }
            else start = mid + 1;
        }

        sum += temp.size() - start;

        return;
    }

    if(!split1[depth].equals("-")){
        func3(depth + 1, key + map.get(split1[depth]));
    }
    else{ // "-" 인 케이스 
        func3(depth + 1, key + "0");
        func3(depth + 1, key + "1");
        if(depth == 0) func3(depth + 1, key + "2");
    }
}

먼저 쿼리를 파싱한다. 

split1 에는 점수를 제외한 값들이 순서대로 들어간다.

0: 언어 1: 직군 2: 경력 3: 소울 푸드

split2 에는 소울 푸드와 점수가 있다 1번 인덱스에 점수가 있다. 

 

이제 백트래킹을 사용해서 key를 만든다 

 

백트래킹을 사용하는 이유는 동적으로 만들어야 하기 때문이다. 

만약 쿼리에 "-" 가 있다면 해당 부분은 모두 허용이기 때문에 모든 경우의 수를 고려해야 한다.

 

그렇게  key를 만들고 만약 해당 key가 존재하지 않는다면 바로 return 

있다면 이제 이분 탐색을 통해서 몇 명이 해당되는지를 최종적으로 구하면 끝이다.

 

1개의 쿼리는 여러개의 key를 만들 수 있다.

그래서 for문의 해당 케이스가 시작할 때 sum을 0으로 초기화하고 

모든 케이스가 끝나면 answer에 기록한다. 

정답 코드 

import java.util.*;
class Solution {
    static HashMap<String, String> map = new HashMap<>();
    static HashMap<String, ArrayList<Integer>> record = new HashMap<>();
    static int sum;
    static String [] split1; // 0: 언어 1: 직군 2: 경력 3: 음식 
    static String [] split2; // 1: 점수 
    public int[] solution(String[] info, String[] query) {
        
        int [] answer = new int [query.length];
        
        init();      // map 초기화 
        func1(info); // info 값 키로 정리 
        func2();     // 이분탐색을 위해서 record value인 리스트 정렬

        for(int i=0; i < query.length; i++){ 
            sum = 0;
            split1 = query[i].split(" and ");
            split2 = split1[3].split(" ");
            split1[3] = split2[0]; 
            func3(0, ""); // 백트래킹을 활용해서 여러가지 경우의 쿼리 만들기 
            answer[i] = sum; // 정답 기록 
        }
        return answer;
    }
    public static void init(){
        map.put("java", "0");
        map.put("cpp", "1");
        map.put("python", "2");
        map.put("backend", "0");
        map.put("frontend", "1");
        map.put("junior", "0");
        map.put("senior", "1");
        map.put("chicken", "0");
        map.put("pizza", "1");
    }
    public static void func1(String[] info){
        for(String temp : info){
            String [] split = temp.split(" ");
            String key = "";
            for(int i = 0 ; i < 4; i++){
                key += map.get(split[i]);
            }
            if(!record.containsKey(key)){
                ArrayList<Integer> list = new ArrayList<>();
                list.add(Integer.parseInt(split[4]));
                record.put(key, list);
            }
            else record.get(key).add(Integer.parseInt(split[4]));
        }
    }
    public static void func2(){  // 정렬 
        Set<String> set = record.keySet();
        for(String key : set){
            Collections.sort(record.get(key));
        }
    }
    public static void func3(int depth, String key){
        if(depth == 4){
            if(!record.containsKey(key)) return;
            
            ArrayList<Integer> temp = record.get(key);
            // 이분 탐색 시작 
            
            int start  = 0;
            int end    = temp.size();
            int target = Integer.parseInt(split2[1]);
            
            while(start < end){
                int mid = (start + end) / 2;
                if(temp.get(mid) >= target){
                    end = mid;
                }
                else start = mid + 1;
            }
            
            sum += temp.size() - start;
             
            return;
        }
        
        if(!split1[depth].equals("-")){
            func3(depth + 1, key + map.get(split1[depth]));
        }
        else{ // "-" 인 케이스 
            func3(depth + 1, key + "0");
            func3(depth + 1, key + "1");
            if(depth == 0) func3(depth + 1, key + "2");
        }
    }
}

1. 순위 검
2. 색

 

1. 순위 검색

•