[2021 KAKAO] 순위검색 - Java코드

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

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

문제

 

설계

반드시 효율성을 고려해서 설계해야한다.

즉, 단순히 배열과 반복문만을 사용하면, INUPT값이 5만 X 10만 X 5개 컬럼별 비교 연산이 일어나므로

최악의 경우, 25억번의 연산이 일어날수있다.

 

포인트

이 문제는 정렬된 배열을 빠르게 탐색할 수 있는, 이진검색 알고리즘으로 풀어야한다.

 

풀이

단순 배열을 순차 접근하여 찾는 경우 

    public static int[] solution(String[] info, String[] query) {
    	int[] answer = new int[query.length];
    	String[][] sup = new String[info.length][5];
    	for(int i=0;i<info.length;i++) // 지원자 점수와 정보 담기
    		for(int j=0;j<5;j++) sup[i][j] = info[i].split(" ")[j];    		
    	for(int i=0;i<query.length;i++) {
    		query[i] = query[i].replaceAll(" and "," ");
    		String[] qry = query[i].split(" ");
    		answer[i] = ResultCount(sup,qry);
    	}
        return answer;
    }
    
    public static int ResultCount(String[][] sup, String[] qry) {
    	int res=0; Boolean flag;
    	for(int i=0;i<sup.length;i++) {
    		flag=true;
    		for(int j=0;j<5;j++) {
    			if(qry[j].equals("-")) continue;
    			else {
    				if(j==4) { // 마지막 컬럼인 스코어는 크거나 같으면 해당됨
    					if(Integer.parseInt(sup[i][j]) >=  Integer.parseInt(qry[j])) 
    						break;
    				}
    				if(!qry[j].equals(sup[i][j])) {
    					flag=false; break;
    				}
    			}
    		}
    		if(flag) res++;
    	}
    	return res;
    }

 

나름 Break를 넣어서 아니면 끝까지 안돌게 해줄려고 했지만,

역시나 효율적이지 못했다.

 

 

정답

효율성을 고려한 이진탐색 풀이 

1. info로 주어지는 데이터들을 공백을 포함한 query에 뽑힐 수 있는 모든 경우의 수를 조합하여 Map에 저장
2. 정렬후 점수 데이터를 통해 이진탐색을 하여 query[]에 해당하는 인원 수를 찾음

import java.util.*;

class Solution {
    static Map<String, ArrayList<Integer>> allInfo;
    static ArrayList<Integer> in;
    public int[] solution(String[] info, String[] query) {
       
        int[] answer = new int[query.length];
        allInfo = new HashMap<>();
        
        // 1. info 모든 경우의 수 map에 저장 
        for(int i=0; i<info.length; i++) {
        	dfs("",0, info[i].split(" "));
        }
        
        // 2. map에 저장된 점수 list 오름차순으로 정렬 	
        List<String> list = new ArrayList<>(allInfo.keySet());
        for(int i=0; i<list.size(); i++) {
        	List<Integer> scoreList = allInfo.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]);

        	answer[i] = search(str[0], score);
        }
        return answer;
    }
	
	
	static void dfs(String pos, int depth, String[] info) {
		
		if(depth == 4) {
			if(!allInfo.containsKey(pos)) {
				in = new ArrayList<>();
				in.add(Integer.parseInt(info[4]));
				allInfo.put(pos, in);
			}else {
				allInfo.get(pos).add(Integer.parseInt(info[4]));
			}
			return;
		}
		dfs(pos+"-", depth+1, info);
		dfs(pos+info[depth], depth+1, info);
		
	}
	
	// 이분 탐색 
	static int search(String str, int score) {
		if(!allInfo.containsKey(str)) return 0;
		List<Integer> scoreList = allInfo.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;
	}
}