[프로그래머스] 2021 KAKAO BLIND RECRUITMENT - "순위 검색" (Java)

 

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

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

순위 검색

---

 

난이도 :  Level 2

 

 정답률 : 정확성 44.07%, 효율성 4.49%인 문제입니다. (카카오 블로그 참고.)

적절한 자료 구조와 다수의 반복문을 통해서 정확성은 통과할 수 있을 것 같습니다. 하지만 효율성 또한 요구하는 문제이므로, 문제에서 의도하는 바를 빠르게 이해하는 것이 관건이라고 생각합니다.  이 문제에서는 "-" 표시를 처리하는 방법과 이분 탐색을 통하여 빠르게 탐색하는 방법을 의도했던 것으로 생각됩니다. 

 

 

 저는 다음과 같이 로직을 설계했습니다.

1. dfs를 통해 info 배열의 각 사용자 정보를 "-" 표시 까지 포함 혹은 포함하지 않은 String 값을 Map 자료구조의 Key 값으로 저장하고 점수는 Map 자료구조의 value 값으로 ArrayList 자료구조를 사용하여 저장할 것.

 

2. 저장 후 각 Key 값을 순회하여 모든 value(ArrayList<Integer>)를 오름차순으로 정렬.

 

3. query 배열의 각 query[i]를  점수와 " and "를 제외한 문자열을 key값으로 정하고 Map 자료구조에 해당 Key 값 대로 value가 잘 나오는지 출력하여 확인.  =>( 여기까지 하면 정확성은 다 맞출수 있습니다. ) 

 

4. 이분 탐색을 통하여 query에 주어진 점수보다 낮은 점수가 존재하는 index를 start에 저장. 

 

 

 

-  static HashMap<String, ArrayList<Integer>> map = new HashMap<>();

 Map의 Key 값으로 "-" 표시를 포함한 모든 경우의 String 값을 저장합니다. info 배열의  “java and backend and junior and pizza 150″ 이라는 String을 탐색할 경우,  Key 값으로 "----" 부터 "javabackendjuniropizza"까지 총 16가지의 경우의 수가 저장됩니다. 

 

 ArrayList<Integer>에는 점수가 저장됩니다. 이미 저장된 key 값에 점수를 추가하기 위해서 List 자료구조를 사용하였습니다.

 

 

 

- static int[] answer;

 다른 함수에서 편하게 answer 변수를 사용하기 위해 전역 변수로 설정하였습니다. 

 

 

 

- int[] Solution(String[] info, String[] query)

 입력을 받고 결과 변수인 answer를 선언합니다. setInfo() 함수와 countQuery() 함수를 호출하는 역할을 합니다. 

그리고 다른 함수에서 설정된 answer 변수를 return 합니다.

 

 

 

- void setInfo(String[] info)

 info 배열의 각 사용자 정보를 dfs 함수를 호출하여 탐색합니다. 탐색이 끝나고 Map 자료구조의 Key 값을 순회하며 Value에 저장된 ArrayList<Integer> 자료구조를 오름차순 정렬합니다. 

 

 

 

- void dfs(String str, int depth, String[] info)

 key 값으로 설정될 str 변수, return의 기준을 잡을 depth 변수, 입력으로 들어온 info배열을 split한 String 배열을 파라미터로 받습니다. 

str 변수에 "-" 값을 더한 dfs 탐색과 split된 info 배열을 더한 dfs 탐색 총 2번을 호출합니다. 이를 통해 모든 경우의 수를 Key 값으로 저장할 수 있습니다. 언어, 직군, 경력, 소울 푸드의 값을 str에 전부 다 저장된 depth의 값은 4이므로 depth가 4가 되면 Map에 저장하거나 기존에 Key 값이 존재하면 점수만 기존에 저장되어 있던 ArrayList에 추가합니다. 

 

 

 

- void countQuery(String[] query)

 입력으로 들어온 query 배열을 탐색합니다. split 함수를 통하여 " and " 와 점수를 제외한 문자열을 key 값으로 저장하였고, 점수는 queryScore 변수에 저장하였습니다. 그 다음 이분 탐색을 통하여 queryScore에 저장된 값보다 작은 값을 start 변수로 지정하고 기존 list의 길이에서 start 값을 빼주어 해당되는 지원자의 수를 구했습니다. 

 

 

  코드

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

public class Solution {
	static HashMap<String,ArrayList<Integer>> map = new HashMap<>();
	static int[] answer;
	
	public static int[] solution(String[] info, String[] query) {
		answer = new int[query.length];
		
		setInfo(info);
		countQuery(query);
		return answer;
	}
	
	public static void setInfo(String[] info) {
		// 모든 경우의 수를 map의 key 값으로 넣어준다.
		for(int i = 0; i<info.length; i++) {
			dfs("", 0, info[i].split(" "));
		}
		// 각 key 값을 돌며 점수를 오름차순 정렬한다. 
		for(String key : map.keySet()) {
			Collections.sort(map.get(key));
		}
	}
	// "-" 혹은 언어, 직군, 경력을 포함한 str을 key 값으로 map에 저장하거나 str이 key 값으로 존재하면 점수만 list에 추가한다.
	public static void dfs(String str, int depth, String[] info) {
		
		if(depth == 4) {
			
			if(!map.containsKey(str)) {
				ArrayList<Integer> list = new ArrayList<>();
				list.add(Integer.parseInt(info[4]));
				map.put(str, list);
			}
			else {
				map.get(str).add(Integer.parseInt(info[4]));
			}
			return;
		}
		
		dfs(str+"-", depth+1, info);
		dfs(str+info[depth], depth+1, info);
	}
    
    	
	public static void countQuery(String[] query) {
		
		for(int i=0; i<query.length; i++) {
			String spl[] = query[i].split(" and ");
			String q = "";
			for(int j=0; j<spl.length; j++) {
				q += spl[j];
			}
			String[] qArr = q.split(" ");
			String key = qArr[0];
			int score = Integer.parseInt(qArr[1]);
			int count = 0;	
			// key 값이 없는 경우로 입력으로 주어질 수도 있다. 런타임 에러를 보기 싫으면 if문을 사용하자.
			if(map.containsKey(key)) {
				ArrayList<Integer> list = map.get(key);
				
				int start = 0; 
				int end = list.size()-1;
				int mid = 0;
                // 이분 탐색. 오름 차순된 list에서 queryScore보다 작은 점수를 start 인덱스로 지정하고 list size에서 start를 빼준다. 
				while(start <= end) {
					mid = (start + end) / 2;
					
					if(list.get(mid) >= score) {
						end = mid - 1;
					}
					else {
						start = mid + 1;
					}
				}
				count = list.size() - start;
			}
			answer[i] = count;
		}
	}
}

 

 

 

피드백 환영합니다.