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

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

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

처음 문제를 보고 생각보다 간단해서 놀랐는데, "효율성"까지 통과해야하는 문제였다

아무생각 없이 구현한 첫 코드는 다음과 같다

import java.util.*;

class Solution {
    public int[] solution(String[] info, String[] query) {
        int[] result = new int[query.length];
		
		int i=0;
		for(String str : query) {
       		// 모두 띄어쓰기로 변경 후 쪼개기
			String[] query_s = str.replaceAll(" and "," ").split(" "); 
			ArrayList<String> arr = new ArrayList<String>();
			
            //효율성을 높이고자 하는 조그만 노력,, length 값 저장
			int size = query_s.length -1;	
			for(int j=0; j<size; j++) {
				arr.add(query_s[j]);
			}
			int n = Integer.parseInt(query_s[size]);
			result[i++] = cnt_person(arr,info, n);
		}
        
        return result;
    }
    
    public int cnt_person(ArrayList<String> arr, String[] info, int n) {
		int cnt = 0;
		int flag = 0;
		
        for(int i=0; i<info.length; i++) {
			String[] info_s = info[i].split(" ");
			flag = 0;
			
			ArrayList<String> arrs = new ArrayList<String>();
			
            for(String str : info_s) {
				arrs.add(str);
			}
			
			int size = arrs.size()-1;
			String number = arrs.get(size);
			for(int j=0; j<size; j++) {
            	// query 배열과 info 배열의 순서가 각각 같기 때문에 해당 인덱스값 비교 
                // 해당 인덱스의 값이 다르더라도 "-"이면 통과 & 아니면 flag값 1로 변경
				if(!arr.get(j).equals(arrs.get(j)) && !arr.get(j).equals("-")) {
					flag = 1;
					break;
				}
			}
            
            // number(마지막 인덱스값)이 "-"가 아닐때, info의 숫자보다 높은지 확인
			if(!number.equals("-")) {
				int num = Integer.parseInt(number);
				if(n > num)
					flag = 1;
			}		
            
            //모든 것을 무사히 통과하고 flag 값이 변하지 않으면 cnt값 1 추가
			if(flag == 0)
				cnt++;
		}

		return cnt;
	}
}

위의 코드로 작성하면 정확도는 100%가 나오지만, 효율성은 극극극악이다

info에서 가장 큰 비중을 차지하는 게 [조건]인데, [조건]이 같고 점수 X가 다른 경우도 각각 따로 저장하기 때문에 효율성도 떨어지고

그만큼 탐색하는데도 오래 걸리고, [조건] 내에서도 각 분야별로 각자 다른 배열로 저장하기 때문에 비효율적이라고 볼 수 있다..

우선 info 배열의 크기는  1이상 50,000이하이고, query의 크기는 1이상 100,000이하이다

효율적으로 바꾸려면

1. info의 [조건] 부분을 하나의 String으로 합치고 코딩테스트 점수 X를 따로 비교해야한다

2. String으로 합치는 과정에서, query가 나타낼 수 있는 모든 경우의 수, 가령 "-"로 나타날 수 있는 모든 경우를 같이 저장한다

3. 같은 [조건]을 여러 번 저장하는 것을 방지하여 Map을 사용하며, Key는 String으로 합친 info의 [조건]을, Value는 [조건]에 해당하는 점수 X를 넣어준다

4. [조건] 부분이 중복되고, 점수 X만 다른 경우를 대비하기 위해 하나의 [조건]에 대한 점수 X는 ArrayList를 사용한다

우선 깊이 우선 탐색을 이용하여 각각의 info에 대하여 개발언어, 직군, 경력, 소울푸드, 점수 를 Map에 저장한다

	public static void dfs(String str, int depth, String[] info) {
		if(depth==4) {
			if(!map.containsKey(str)) {
				arr = new ArrayList<>();
				arr.add(Integer.parseInt(info[4]));
				map.put(str, arr);
			}
			else {
				map.get(str).add(Integer.parseInt(info[4]));
			}
			return ;
		}
		dfs(str+"-",depth+1, info);
		dfs(str+info[depth],depth+1, info);
	}

str에는 내용이 없는 문자열 ""이 들어오고, info는 각 info를 split(" ")으로 자른 배열이 들어온다

재귀호출을 통해 조건 4개와 점수 1개를 이용한 모든 경우(각 부분을 "-"로 대체한 경우)를 map에 저장한다

다음 info 에서 같은 [조건]에 다른 점수가 나왔을 때는 Value에 있는 ArrayList에 점수만 추가하면 된다

-

이제 query를 보고 각 query마다 해당하는 사람이 몇 명이 있는지 확인해야 하는데,

Map의 Key 값은 String이기 때문에, 바로 확인 할 수 있지만 Value 값은 ArrayList로 선언되어 있기 때문에 다시 탐색해야 한다

		ArrayList<String> list = new ArrayList<String>(map.keySet());
		for(int i=0; i<list.size(); i++) {
			ArrayList<Integer> scoreList = map.get(list.get(i));
			Collections.sort(scoreList);
		}

우선 탐색하기 쉽게 Collections의 기능인 sort를 이용하여 크기 순으로 정렬한 다음 효율성이 좋은 이진 탐색을 진행한다

	public static int search(String str, int score) {
		if(!map.containsKey(str)) return 0;
		
		ArrayList<Integer> scoreList = map.get(str);
		int start =0, end = scoreList.size()-1;
		while(start <= end) {
			int mid = (start+end)/2;
			if(scoreList.get(mid) < score) {
				start = mid+1;
			}else {
				end = mid-1;
			}
		}
		return scoreList.size()-start;
	}

해당 [조건]이 없으면 바로 0을 리턴하고, 만약 있다면 start와 end를 각각 0과 끝(인덱스마지막)으로 지정하여 탐색한다

start와 end의 값이 만나는 지점이 바로 score의 값보다 큰 값들 중에 최저값이다

따라서 X의 개수 중에 최종 start 값을 빼주면 score 값보다 큰 값들의 개수가 나오게 된다

최종 코드는 다음과 같다

import java.util.*;


public class Solution{
	static Map<String, ArrayList<Integer>> map;
	static ArrayList<Integer> arr;
	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"};
		
		int[] result = new int[query.length];
		map = new HashMap<>();
		
		for(int i=0; i<info.length; i++) {
			dfs("",0,info[i].split(" "));
		}
		
		ArrayList<String> list = new ArrayList<String>(map.keySet());
		for(int i=0; i<list.size(); i++) {
			ArrayList<Integer> scoreList = map.get(list.get(i));
			Collections.sort(scoreList);
		}
		
		for(int i=0; i<query.length; i++) {
			query[i] = query[i].replaceAll(" and ", "");
			String[] str = query[i].split(" ");
			int score = Integer.parseInt(str[1]);
			
			result[i] = search(str[0], score);
			System.out.println(result[i]);
		}

	}
	
	public static void dfs(String str, int depth, String[] info) {
		if(depth==4) {
			if(!map.containsKey(str)) {
				arr = new ArrayList<>();
				arr.add(Integer.parseInt(info[4]));
				map.put(str, arr);
			}
			else {
				map.get(str).add(Integer.parseInt(info[4]));
			}
			return ;
		}
		dfs(str+"-",depth+1, info);
		dfs(str+info[depth],depth+1, info);
	}
	
	public static int search(String str, int score) {
		if(!map.containsKey(str)) return 0;
		
		ArrayList<Integer> scoreList = map.get(str);
		int start =0, end = scoreList.size()-1;
		while(start <= end) {
			int mid = (start+end)/2;
			if(scoreList.get(mid) < score) {
				start = mid+1;
			}else {
				end = mid-1;
			}
		}
		return scoreList.size()-start;
	}

}

 

깊이 우선 탐색과 이진 탐색을 모르는 것이 절대 아닌데, 막상 문제에 적용하려니 너무 어렵고,, 힘들었다

밑에 참조되어 있는 링크의 코드를 정독하면서 계속해서 이해하려고 하고, 왜 이렇게 작성했는지 기존에 내가 작성한 코드는 무엇이 문제였는지 계속 생각하게 된 시간이었다.. 이틀에 걸쳐 통과한 문제이니 주기적으로 돌아보고 반성하면서 공부해야겠다

 

참조!

https://loosie.tistory.com/265