[프로그래머스] level2. 순위 검색 (자바 JAVA)

[ 문제 ]  [프로그래머스] level2. 순위 검색 (자바 JAVA)

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/72412

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

---

# 접근 방법 및 풀이 

 

• 문제 자체는 어렵지 않지만, 효율성 통과하기 어려운 코드였다. 초기에 시도하고 포기하다가 오랜만에 다시 풀었다.
• info 배열의 최대 크기는 5만, query배열의 최대 크기는 10만이므로, 최대 50억번 반복할 수 있기때문에 그냥 차례대로 비교한다면 시간 초과가 난다. 이걸 해결하는 부분이 핵심이다.
• 처음엔 점수 찾는 부분을 단순히 이분탐색으로 하면 되겠지 했는데 역시나 시간초과다.
• 그래서 접근한 방식은 먼저, HashMap을 사용해 info[] 배열에 주어진 조건으로 만들 수 있는 "개발언어, 직군, 경력, 소울푸드" 조합을 key로 만들어 저장한다. 이때, value는 List<Integer> 형태로 해당 조합조건에 맞는 점수들을 list에 add한다.
• 예를들어 info[0] = "java backend junior pizza" 라고 한다면, 주어진 4개의 조건으로 만들 수 있는 조합은 다음과 같다.
• 2^4 = 16개, 즉 부분집합이다. 이때 key는 String형태로 선택하지 않으면 "-"로, 선택하면 해당 String을 더한 형태로 만들어 준다.
• ex) "----" or "java-junior-" or "java---"
• 그리고 key값에 따른 점수 List를 오름차순으로 정렬한다. 왜냐하면 이분탐색으로 원하는 점수 이상인 것을 더 빨리 뽑을 것이기 때문이다.
• 근데 여기서 중요한건, query배열의 쿼리를 split을 이용해 key로 만들어 준 후, map에서 key값을 이용해 value를 뽑고, value가 List니까 그때마다 Collection.sort()를 시켜줬는데, 이렇게 하면 시간 초과가 난다. (코드상 주석 친 부분)
•  ..? 뭐지?
• 그래서 따로 for-each문으로 map의 keySet()을 이용해 key값 불러와서 List들을 오름차순 정렬 먼저 다 시켜주고 했더니 이번엔 통과다.
• 당황스럽네.. 같은 로직인데 먼저 정렬을 다 해주냐, map.get(key)해서 가져온 리스트를 하나씩 정렬해주냐에 따라 속도 차이가 있다. 
• 자세한건 코드참조

# 주의할 점 

 

• key값에 따른 점수 List 먼저 정렬 다 해줄것. map.get(key)해서 list 불러오고 하나씩 정렬하면 시간초과남.
• map.get(key) 했을 때 해당 key값에 따른 value인 list가 없으면 당연히 null이다. 여기서 list.size()하면 당연히 NullPointerException남. info 조건에 따른 조합을 만들었어도, 쿼리에 해당하는 조건이 info 조합에 없을 수도 있다. 그때 해당 key값이 없어 null이게 되므로 이부분 확인하기.
• 이분 탐색에서 사소한 실수 인데, int mid = (start + end) / 2; <- 이 부분에서 괄호 안 쳐주면 당연한 소리지만 무한루트 돈다. / 연산이 우선순위가 더 높기 때문이다. 실수로 괄호 치는거 빼먹었다.

 

JAVA 코드

import java.util.*;
class Solution {
	static HashMap<String, List<Integer>> map;
	public static int[] solution(String[] info, String[] query) {
		int[] answer = new int[query.length];
		map = new HashMap<String, List<Integer>>();
		for (int i = 0; i < info.length; i++) {
			powerSet(0, "", info[i].split(" "));
		}
        for (String key : map.keySet()) {
			Collections.sort(map.get(key));
		}
		for (int i = 0; i < query.length; i++) {
			String arr[] = query[i].split(" and | ");
			String key = String.join("", arr[0], arr[1], arr[2], arr[3]);
			List<Integer> list = map.getOrDefault(key, new ArrayList<Integer>());
			//Collections.sort(list);
			int score = Integer.parseInt(arr[4]);
			int start = 0; 
			int end = list.size();
			while( start < end) {
				int mid = (start + end) / 2;
				if(list.get(mid) < score) 
					start = mid +1;
				else
					end = mid;
			}
			answer[i] = list.size() - start;
		}
		return answer;
	}
	private static void powerSet(int idx, String s, String arr[]) {
		if(idx == 4){
			map.computeIfAbsent(s, k -> new ArrayList<Integer>()).add(Integer.parseInt(arr[4]));
			return;
		}
		powerSet(idx+1, s + arr[idx], arr);
		powerSet(idx+1, s+"-", arr);
	}
}

 

 

 

REVIEW

너무 좋은 문제인데, 내가 짠 코드는 겨우 통과하는 코드다. 소팅을 먼저 다 해주냐, 따로 하나씩 해주냐에 따라 효율성 차이가 있는거 보면.. ㅠㅠ 비트마스킹으로 key조합 만들어 내는 것도 있는데 그부분 연구해봐야겠다.