[프로그래머스] 순위검색 - 2021 KAKAO BLIND RECRUITMENT

문제 - 프로그래머스 Lv2 

 

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

프로그래머스

 

 

날짜 : 2024-04-08

후기

 - split vs StringTokenizer 비교하며 확인하기

 - 문자열 문제는 HashMap을 적극적으로 활용하기(value에 ArrayList를 넣을 수 있음)

 - 순-조-부 + 이분탐색(데이터 크기 확인하기) 자주 나옴

풀이 과정 : 문자열 파싱 & 부분 조합 & 이분 탐색 (1h,  ★★★☆☆)

입력값 예시

입력값 예시 2

 

처음에 배열에 저장해서 반복문을 돌며 검사했더니, 테스트 케이스는 모두 맞았지만 효율성 테스트에서 오답이 나왔다. 따라서 시간을 줄이기 위해 HashMap & Combination & BinarySearch 를 사용했다.

 

1. HashMap

HashMap 의 Key 는 점수를 제외한 문자열, value는 ArrayList<Integer> 형식으로 넣어주었다. 

(hmap의 값 존재 여부를 확인할 때, hmap.containsKey(key) 를 적극적으로 활용하기)

 

static HashMap<String, ArrayList<Integer>> hmap = new HashMap<>();

 

    if(hmap.containsKey(str)){
        hmap.get(str).add(score);
    }else{
        ArrayList list = new ArrayList<>();
        list.add(score);
        hmap.put(str, list);
    }

 

 

2. Combination

HashMap에 넣어줄 때 애초에 key 값으로 입력값이 들어온 것과 - 로 들어온 것, 두 가지 경우를 모두 다 넣어주었다(부분집합). 따라서 4가지 속성인 결과로는 총 16가지의 결과값이 나오게 된다.

 

    // 가능한 모든 문자열 조합
    public void Combi(String[] p_info, String str, int depth){
        
        if(depth == 4){
            int score = Integer.parseInt(p_info[depth]);
            System.out.println("str : " + str);
            
            if(hmap.containsKey(str)){
                hmap.get(str).add(score);
            }else{
                ArrayList list = new ArrayList<>();
                list.add(score);
                hmap.put(str, list);
            }
            
            return;
        }
        Combi(p_info, str+"-", depth+1);
        Combi(p_info, str+p_info[depth], depth+1);
    }

 

 

3. BinarySearch

마지막 입력 값이 소울푸드 + 점수의 형식으로 들어오기 때문에 파싱의 과정이 한번 더 필요하다. 

따라서 언어 + 직군 + 경력 + 소울푸드를 key값으로 하는 values를 확인해야 한다.

 

start 는 0, end는 해당 query에 맞는 ArrayList의 크기로 초기 설정 해준 뒤, 이분탐색을 진행한다.

return은 전체 size에서 start를 빼준 값으로 인덱스(조건에 맞는 값이 몇 개나 있는지 확인)를 확인하는 역할을 한다.

public int BinarySearch(String query){
    String[] str = query.split(" and ");
    int score = Integer.parseInt(str[3].split(" ")[1]);

    String cur_query = str[0] + str[1] + str[2] + str[3].split(" ")[0];

    if(!hmap.containsKey(cur_query)) return 0;

    ArrayList<Integer> scores = hmap.get(cur_query);
    int start = 0;
    int end = scores.size();

    while(start < end){

        int mid = (start + end) / 2;

        if(scores.get(mid) >= score){
            end = mid;
        }else{
            start = mid + 1;
        }
    }
    return scores.size() - start;
}

 

 

<전체 코드>

import java.util.*;

class Solution {
    
    static HashMap<String, ArrayList<Integer>> hmap = new HashMap<>();
    
    public int[] solution(String[] info, String[] query) {
        
        for(int i = 0; i < info.length; i++){
            Combi(info[i].split(" "), "", 0);
        }
        
        // 이분탐색을 위해 정렬
        for(ArrayList list : hmap.values()){
            Collections.sort(list);
        }
        
        int[] answer = new int[query.length];
        
        for(int i = 0; i < query.length; i++){
            answer[i] = BinarySearch(query[i]);
        }
        return answer;
    }
    
    public int BinarySearch(String query){
        String[] str = query.split(" and ");
        int score = Integer.parseInt(str[3].split(" ")[1]);
        
        String cur_query = str[0] + str[1] + str[2] + str[3].split(" ")[0];
        
        if(!hmap.containsKey(cur_query)) return 0;
        
        ArrayList<Integer> scores = hmap.get(cur_query);
        int start = 0;
        int end = scores.size();
        
        while(start < end){
            
            int mid = (start + end) / 2;
            
            if(scores.get(mid) >= score){
                end = mid;
            }else{
                start = mid + 1;
            }
        }
        return scores.size() - start;
    }
    
    // 가능한 모든 문자열 조합
    public void Combi(String[] p_info, String str, int depth){
        
        if(depth == 4){
            int score = Integer.parseInt(p_info[depth]);
            //System.out.println("str : " + str);
            
            if(hmap.containsKey(str)){
                hmap.get(str).add(score);
            }else{
                ArrayList list = new ArrayList<>();
                list.add(score);
                hmap.put(str, list);
            }
            
            return;
        }
        Combi(p_info, str+"-", depth+1);
        Combi(p_info, str+p_info[depth], depth+1);
    }
}

채점 결과