[Programmers] 순위 검색

[문제 링크]

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

프로그래머스

 

 

[풀이 과정]

말이 필요 없습니다.

한 번 보세요..

보고 스스로 몇번 풀다보니 이해됬습니다.

 

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

 

 

[코드]

import java.util.*;

class Solution {
    public int[] solution(String[] info, String[] query) {
        Map<String, List<Integer>> hashMap = new HashMap<>();
        
        // 문자열 정리
        for(String s : info) {
            String[] data = s.split(" ");
            String[] languages = {data[0], "-"};
            String[] jobs = {data[1], "-"};
            String[] exps = {data[2], "-"};
            String[] foods = {data[3], "-"};
            Integer score = Integer.parseInt(data[4]);
            
            // 모든 경우의 수를 hashMap의 key로 저장 후 value는 그 사람의 score
            for(String language : languages) {
                for(String job : jobs) {
                    for(String exp : exps) {
                        for(String food : foods) {
                            String[] keys = {language, job, exp, food};
                            String key = String.join(" ", keys);
                            List<Integer> arr = hashMap.getOrDefault(key, new ArrayList<Integer>());
                            arr.add(score);
                            
                            hashMap.put(key, arr);
                        }
                    }
                }
            }
        }
        
        // 이분탐색을 위한 오름차순 정렬
        for(List<Integer> arr : hashMap.values()) {
            Collections.sort(arr);
        }
        
        int[] answer = new int[query.length];
        int i = 0; // 인덱스마다 값 넣어주려고
        
        // query 정리
        for(String q : query) {
            String[] data = q.split(" and ");
            Integer targetScore = Integer.parseInt(data[3].split(" ")[1]); // 점수 뽑아낸 뒤
            data[3] = data[3].split(" ")[0]; // 음식으로 설정
            String key = String.join(" ", data);
            
            // 키 값이 있으면 이분 탐색 시작
            if(hashMap.containsKey(key)) {
                List<Integer> list = hashMap.get(key);
                
                int left = 0;
                int right = list.size();
                
                while(left < right) {
                    int mid = (left + right) / 2;
                    
                    if(list.get(mid) >= targetScore) {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                }
                answer[i] = list.size() - left;
            }
            i++;
        }
        
        return answer;
    }
}

[회고]

21년도에 카카오에서 이런 문제를 블라인드 테스트에서 냈다고 하네요.

지금은 더 어렵겠죠?

더 열심히 해야겠습니다..

어렵네요

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.