[Programmers] 순위 검색

문제

 

2021 KAKAO BLIND RECRUITMENT > 순위 검색

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

 

 

아이디어

 

이 문제를 풀기 위해 가장 중요한 것은 이분 탐색을 할 수 있냐, 없냐 인 것 같습니다.

 

지원서에 입력되는 4가지 값을 구분하며 점수를 입력하는 방법은 배열을 이용하는 방법, Map을 이용하는 방법 등 다양한 방법들이 있습니다.

 

아마 저를 포함하여 대다수의 알고리즘 문제들을 풀어본 분들은 위의 방법들을 이용하여 점수 분류를 수월하게 했겠지만 문제를 제출했을 때 돌아온 답변은 시간 초과였을 것입니다.

 

그리고 시간 초과가 나신 분들은 query에 해당하는 점수보다 크거나 같은 값을 찾을 때 점수 리스트를 단순 반복문을 이용하여 찾으셨을 것입니다.

 

저도 단순 반복문을 쓰면서 조금 찝찝한 느낌이 있었는데 역시나 시간 초과가 저를 반겼고 시간 초과가 나지 않도록 하기 위해 info를 탐색하며 점수를 추가할 때마다 sorting을 한 뒤 query에 해당하는 점수 조건을 찾을 때 이분 탐색을 사용했습니다.

 

결과적으로 코드 구현은 다음과 같은 절차를 기반으로 구현하게 되었습니다. 

 

1. 점수들을 담는 배열을 생성한 뒤 info를 순회하며 점수를 저장 (+sorting)

2. query의 인덱스를 탐색

3. query 정보에 맞는 점수 리스트 찾기

4. 이분 탐색을 이용하여 해당 점수 이상인 사람 수 찾기

5. 모든 인덱스를 탐색할 때 까지 2~4를 반복

 

 

구현 코드 (Java)

 

import java.util.*;

class Solution {
    public int[] solution(String[] info, String[] query) {
        List<Integer> list[][][][] = new List[3][2][2][2]; // 점수를 담는 리스트 배열
        
        for(int i=0; i<3; i++) {
        	for(int j=0; j<2; j++) {
        		for(int k=0; k<2; k++) {
        			for(int a=0; a<2; a++) {
        				list[i][j][k][a] = new ArrayList<Integer>();
        			}
        		}
        	}
        }
        
        for(int i=0; i<info.length; i++) {
        	String split[] = info[i].split(" ");
        	int langIndex = getIndex(split[0], 0);
        	int fieldIndex = getIndex(split[1], 1);
        	int levelIndex = getIndex(split[2], 2);
        	int foodIndex = getIndex(split[3], 3);
        	int score = Integer.valueOf(split[4]);
        	
            	// 리스트에 점수를 추가할 때마다 오름차순으로 정렬
        	list[langIndex][fieldIndex][levelIndex][foodIndex].add(score);
        	list[langIndex][fieldIndex][levelIndex][foodIndex].sort(new Comparator<Integer>() {
        		@Override
        		public int compare(Integer o1, Integer o2) {
        			return o1-o2;
        		}
			});
        }
        
        int res[] = new int[query.length];
        
        for(int i=0; i<query.length; i++) {
        	String split[] = query[i].split(" and ");
        	String split2[] = split[3].split(" ");
        	
            	// 문자가 '-'일 경우 index값은 -1로 리턴
        	int langIndex = getIndex(split[0], 0);
        	int fieldIndex = getIndex(split[1], 1);
        	int levelIndex = getIndex(split[2], 2);
        	int foodIndex = getIndex(split2[0], 3);
        	int score = Integer.valueOf(split2[1]);
        	
            	// 사람 수의 합
        	int sum = 0;
        	
            	// 각 인덱스 별로 index값이 -1이면 모든 범위, -1이 아니면 해당 값에 대해서만 순회
        	for(int j=(langIndex == -1 ? 0 : langIndex); j<=(langIndex == -1 ? 2 : langIndex); j++) {
        		for(int k=(fieldIndex == -1 ? 0 : fieldIndex); k<=(fieldIndex == -1 ? 1 : fieldIndex); k++) {
        			for(int a=(levelIndex == -1 ? 0 : levelIndex); a<=(levelIndex == -1 ? 1 : levelIndex); a++) {
        				for(int b=(foodIndex == -1 ? 0 : foodIndex); b<=(foodIndex == -1 ? 1 : foodIndex); b++) {
        					List<Integer> targetList = list[j][k][a][b];
        					
        					if(targetList.size() > 0) { // 담겨있는 점수가 존재할 경우
        						int start = 0;
            					int end = targetList.size()-1;
            					
            					while(start <= end) { // 이분 탐색
            						int mid = (start+end)/2;
            						
            						if(targetList.get(mid) < score) {
            							start = mid+1;
            						} else {
            							end = mid-1;
            						}
            					}
            					
            					sum = sum + (targetList.size() - start);
        					}
        				}
        			}
        		}
        	}
        	
        	res[i] = sum;
        }
        
        return res;
    }
    
    public static int getIndex(String str, int index) { // 문자를 인덱스로 변환하여 리턴
    	if(index == 0) {
    		switch(str) {
    		case "cpp":
    			return 0;
    		case "java":
    			return 1;
    		case "python":
    			return 2;
    		}
    	} else if(index == 1) {
    		switch(str) {
    		case "backend":
    			return 0;
    		case "frontend":
    			return 1;
    		}
    	} else if(index == 2) {
    		switch(str) {
    		case "junior":
    			return 0;
    		case "senior":
    			return 1;
    		}
    	} else if(index == 3) {
    		switch(str) {
    		case "chicken":
    			return 0;
    		case "pizza":
    			return 1;
    		}
    	}
    	
    	return -1;
    }
}

 

 

읽어주셔서 감사합니다.