[프로그래머스 - java] 순위 검색

문제

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

설명

조합과 이분탐색을 사용하면 금방 해결되는 문제였다.

1. info배열에 있는 조건들로 만들 수 있는 모든 경우의 수를 구해 특정 조건에 해당하는 점수를 리스트로 만들어서 Map<key(조건), value(조건을 만족하는 점수 리스트)>을 생성한다. -> comb()
2. 이분탐색으로 query배열에 있는 조건을 만족하는 list.size()를 구한다. -> binarySearch()

주의할 점
이분탐색은 정렬된 데이터에서만 가능하기 때문에 query배열에 있는 조건을 만족하는 인원 수를 구하기 전에 Map의 각 조건(key)에 해당하는 점수 리스트(value)를 오름차순 정렬 해주어야 한다.

소스코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;

public class RankingSearch {

	static HashMap<String, ArrayList<Integer>> map;
	
	public static void main(String[] args) {
		String[] info = {"java backend junior pizza 150", "python frontend senior chicken 210", "python frontend senior chicken 150", 
				"cpp backend senior pizza 260", "java backend junior chicken 80", "python backend senior chicken 50"};
		
		String[] query = {"java and backend and junior and pizza 100", "python and frontend and senior and chicken 200",
				"cpp and - and senior and pizza 250", "- and backend and senior and - 150", "- and - and - and chicken 100", "- and - and - and - 150"};
		
		System.out.println(Arrays.toString(solution(info, query)));
	}
	
	public static int[] solution(String[] info, String[] query) {
		map = new HashMap<>();
		
		for (String s : info) {
			comb(s.split(" "), 0, ""); // 공백 제거
		}
		
		// 점수 오름차순 정렬
		for (String key : map.keySet()) {
			Collections.sort(map.get(key));
		}
		
		ArrayList<Integer> answer = new ArrayList<>();
		
		for (String s : query) {
            // map의 key에 조건이 공백 없이 들어가 있으므로 and와 공백을 제거
			String[] split = s.replaceAll(" and ", "").split(" "); // 조건과 점수를 구분
			answer.add(binarySearch(split[0], Integer.parseInt(split[1])));
		}
		
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
	
	// 모든 경우의 수에 해당하는 점수 구하기, infoArr로 만들 수 있는 모든 경우의 수를 구함
	public static void comb(String[] infoArr, int depth, String str) {
		if (depth == 4) {
			int score = Integer.parseInt(infoArr[4]);
			
			if (map.containsKey(str)) {
                // key가 존재하는 경우 점수를 리스트에 추가
				map.get(str).add(score);
			} else {
                // key가 존재하지 않는 경우에는 리스트를 만들어서 map에 추가
				ArrayList<Integer> list = new ArrayList<>();
				list.add(score);
				map.put(str, list);
			}
			
			return;
		}
		
		comb(infoArr, depth + 1, str + "-");
		comb(infoArr, depth + 1, str + infoArr[depth]);
	}
	
	// 이분탐색
	public static int binarySearch(String key, int score) {
		// 해당 조건을 만족하는 점수가 없을 경우에는 return 0
		if (!map.containsKey(key)) {
			 return 0;
		}
		
		ArrayList<Integer> list = map.get(key);
		
		int start = 0;
		int end = list.size() - 1;
		
		while (start <= end) {
			int mid = (start + end) / 2;
			
			if (list.get(mid) < score) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		
		return list.size() - start;
	}

}

GITHUB

https://github.com/MinchaeKwon/Programmers/blob/master/2021_Kakao_Blind_Recruitment/src/RankingSearch.java