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

🔗 문제 링크

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

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

 

📝 풀이 과정

효율성이 뚫기 어려운 문제였다. info도 5만개면서, query의 수도 10만개이기 때문에 단순 검색으로는 불가능해 이분탐색을 활용하였다.

• 점수를 제외한 info로 가능한 모든 조합을 구해 key를 만든다
• 구한 key 마다 List를 생성해 점수를 add
• 점수 List를 오름차순 정렬
• query에서 '-'를 제외한 조건으로 key를 만들고 점수 List를 가져온다
• 이분탐색을 통해 주어진 점수 이상인 사람들의 수를 센다

 

 

key별로 점수 List를 가지기 위해 Map<String, List<Integer>> infos를 생성하였다.

 

for (int i = 0; i < (1 << 4); i++) {
  StringBuilder key = new StringBuilder();
  
  for (int j = 0; j < 4; j++) {
      if ((i & (1 << j)) > 0) key.append(split[j]);
  }
  infos.computeIfAbsent(key.toString(), s -> new ArrayList<>()).add(score);
}

비트연산을 통해 조건으로 조합할 수 있는 key가 가능한 모든 조합을 구했다. i가 $1001_2$이면 0번과 3번 인덱스에 해당하는 조건이 선택되어 조합을 만들게 된다.

만들어진 key를 infos에 넣어야 하는데 만약 새로운 key가 나와 기존에 값이 없다면 NullPointerException이 발생하게 된다. 따라서 computeIfAbsent() 메서드를 활용해 value가 없다면 새로운 ArrayList를 생성하고 생성한 List에 점수를 넣어주었다.

 

조합이 끝나면 만들어진 모든 List를 정렬하고, query마다 받은 조건을 통해 key를 생성해주고 key에 해당하는 List를 받아온다. 만약 key가 기존에 없던 새로운 조건들로만 이루어졌다면 null이 반환되기 때문에 getOrDefault()메서드를 통해 빈 List를 반환하였다.

 

정렬되어 있는 List에서 조건 점수가 해당하는 값의 이분탐색을 통해 lower_bound(값이 일치하는 인덱스 중 가장 작은 값)을 찾아 List의 size에서 빼주면 점수 이상인 사람의 수가 나오게 된다.

 

💻 코드

import java.util.*;

public class Solution {
    public int[] solution(String[] info, String[] query) {
        Map<String, List<Integer>> infos = new HashMap<>();
        for (String in : info) {
            String[] split = in.split(" ");
            int score = Integer.parseInt(split[4]);

            for (int i = 0; i < (1 << 4); i++) {
                StringBuilder key = new StringBuilder();
                for (int j = 0; j < 4; j++) {
                    if ((i & (1 << j)) > 0) key.append(split[j]);
                }
                infos.computeIfAbsent(key.toString(), s -> new ArrayList<>()).add(score);
            }
        }

        List<Integer> empty = new ArrayList<>();
        for (Map.Entry<String, List<Integer>> entry : infos.entrySet())
            entry.getValue().sort(null);

        int[] answer = new int[query.length];
        for (int i = 0; i < query.length; i++) {
            String[] split = query[i].replaceAll("-", "").split(" and | ");
            String key = String.join("", split[0], split[1], split[2], split[3]);
            int score = Integer.parseInt(split[4]);
           
            List<Integer> list = infos.getOrDefault(key, empty);

            int s = 0, e = list.size();

            while (s < e) {
                int mid = (s + e) / 2;

                if (list.get(mid) < score) s = mid + 1;
                else e = mid;
            }

            answer[i] = list.size() - s;
        }

        return answer;
    }
}