[Algorithm] Programmers_순위 검색 in Java

💡 Programmers Lv2. 순위 검색:

map을 활용하여 지원자 info에 대한 모든 조합을 정리 후 이분 탐색을 통해 값 찾기

🌱 코드 in Java

알고리즘: DFS

import java.util.*;

class Solution {
    Map<String, List<Integer>> map = new HashMap<>();
    
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        for (String i : info) {
            String[] applicant = i.split(" "); // 공백을 기준으로 split
            comb(applicant, "", 0); // "----" "java---", "javajunior--"와 같은 형태로 한 지원자에게서 나올 수 있는 모든 조건에 대해 dfs로 문장 구성
        }
        
        for (String key : map.keySet())
            Collections.sort(map.get(key)); // 이분 탐색을 위해 점수값 정렬
        
        for (int i = 0; i < query.length; i++) {
            query[i] = query[i].replaceAll(" and ", ""); // 조건과 점수 분리를 위해 문장 치환
            String[] c = query[i].split(" "); // 공백을 기준으로 split
            answer[i] = map.containsKey(c[0]) ? binSearch(c[0], Integer.parseInt(c[1])) : 0; // query와 일치하는 지원자 정보가 없을 경우 0, 있을 경우 이분 탐색을 통해 지원자 수 확인
        }
        return answer;
    }
    
    public void comb(String[] applicant, String str, int cnt) {
        if (cnt == 4) {
            if (!map.containsKey(str)) // key가 없을 경우
                map.put(str, new ArrayList<Integer>()); // 새 리스트 생성하여 밸류에 추가
            map.get(str).add(Integer.parseInt(applicant[4])); // 해당 키의 리스트에 지원자 점수 추가
            return;
        }
        comb(applicant, str + "-", cnt + 1); // "-" 조건 추가
        comb(applicant, str + applicant[cnt], cnt + 1); // 실제 지원자의 조건 추가
    }

    public int binSearch(String k, int con) {
        List<Integer> list = map.get(k); // query에 해당하는 리스트 조회
        int left = 0, right = list.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (con > list.get(mid)) // 쿼리 조건 점수보다 중앙값이 작을 경우 그 이하를 버림
                left = mid + 1; // left를 작을때보다 하나 많게 설정하여 찾고자 하는 값과 같거나 그 값보다 큰 첫번째 경우의 인덱스를 찾을 수 있도록 함
            else
                right = mid; // 쿼리 조건 점수보다 중앙값이 크거나 같을 경우 작은 경우를 찾을 수 있도록 범위 축소를 위해 right를 mid로 변경
        }
        return list.size() - left; // 리스트 사이즈에서 첫번째 인덱스를 빼 갯수 계산
    }
}

이번 문제는 dfs를 통해 지원자별 모든 조건을 map로 하는 것까지는 떠올렸는데,
이분 탐색을 떠올리지 못해 시간초과 + 효율성에서 처음에 실패했었다.

입력 제한사항 크기가 커서 당연히 전체 순회를 하면 안 될 것 같았는데,
왜 이분 탐색을 떠올리지 못하는 건지! 또르륵.

이분 탐색, 슬라이딩 윈도우 이런 식으로 범위를 한정하여 탐색하는 방법들을
잘 생각해놓자!

🧠 기억하자

1. str.replaceAll("치환대상", "치환할단어");

• 이 경우 기존 문장이 변경되지 않으니 기존 문장을 변경하고 싶을 경우 대입해 주어야 함