2021 KAKAO BLIND RECRUITMENT : 순위 검색(비트마스크 & 집합)

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

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

 

// 접근법

 

// 코드

import java.util.*;
 
class Solution {
    
    Map<String, Integer> Wordmap   = new HashMap<>();
    List<List<Integer>> Scorelist = new ArrayList<>();
    
    public int[] solution(String[] info, String[] query) {
        
        Wordmap.put("-", 0);
        Wordmap.put("cpp", 1);
        Wordmap.put("java", 2);
        Wordmap.put("python", 3);
        Wordmap.put("backend", 1);
        Wordmap.put("frontend", 2);
        Wordmap.put("junior", 1);
        Wordmap.put("senior", 2);
        Wordmap.put("chicken", 1);
        Wordmap.put("pizza", 2);
        
        for(int i=0; i<(4*3*3*3); ++i)
            Scorelist.add(new ArrayList<>());
        
        for(String str : info) {
            
            String[] word = str.split(" ");
            
            int[] arr = {
                Wordmap.get(word[0]) *3*3*3,
                Wordmap.get(word[1]) *3*3,
                Wordmap.get(word[2]) *3,
                Wordmap.get(word[3])
            };
            
            int score = Integer.parseInt(word[4]);
                                    
            for(int i=0; i<(1 << 4); ++i) {
                int idx = 0;
                for(int j=0; j<4; ++j) {
                    if( (i & (1<<j)) != 0)
                        idx += arr[j];
                }
                Scorelist.get(idx).add(score);
            }
        }
        
        // 이진 탐색을 하기 위해 정렬을 해준다.
        for(int i=0; i<4*3*3*3; ++i) 
            Collections.sort(Scorelist.get(i)); 
        
        int[] answer = new int[query.length];
        for(int i=0; i<query.length; ++i) {
            String[] word = query[i].split(" ");
            
            int idx = (Wordmap.get(word[0]) *3*3*3)
                + (Wordmap.get(word[2]) *3*3)
                + (Wordmap.get(word[4]) *3)
                + Wordmap.get(word[6]);
            
            int score = Integer.parseInt(word[7]);            
            int ret = Collections.binarySearch(Scorelist.get(idx), score);
 
            if(ret < 0) {
                ret = -(ret + 1);
            } else {
                // 같은 수일 경우 가장 낮은 개수를 찾기 위해
                // 예 - - - - 150 일 때 50 80 150 150 210 260 인경우
                // 만약 ret에는 3번째에 위치한 150을 가르키게되어 150 이상의 값을 구하면 3이된다.
                // 즉 이전의 150의 값은 누락되는 것이다. 그래서 이러한 누락을 방지하기 위해 아래와 같은 작업을 해준다.
                // 주어진 입출력에서는 사실상 문제가 없다. 
                for(int j = ret - 1; j >= 0; --j) {
                    if(Scorelist.get(idx).get(j) == score) ret = j;
                    else break;                    
                } 
                 
            }
            answer[i] = Scorelist.get(idx).size() - ret;
        }
        
        return answer;
    }
}

 

// 비트 연산자 개념

https://www.youtube.com/watch?v=rwxqCSAiuS4&t=753s