[2021 KAKAO BLIND RECRUITMENT] 순위 검색 - JAVA

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

프로그래머스

---

이 문제는 효율성을 만족시키는게 관건..이었다고 한다

난 구현도 못했는디..

구현하면서 단순 반복문으로 비교하면 시간 초과가 날 것 같았다

그냥 그건 그럴 것 같았음

그래서 찾아본 결과!! info가 만들 수 있는 모든 경우의 수의 문자열을 만들어서 map의 key로 넣고, 점수를 value로 넣어준다

이 때 생성된 문자열은 중복될 수 있으니까 점수는 리스트 형태로 넣어준다 (여러개가 될 수 있으니까)

그리고 query를 key로 하는 value들을 가져와서 이분탐색한다

 

즉! 키워드는 모든 조합의 map과 이분탐색이다!!

 

 

1) 모든 조합의 문자열을 생성하는 메서드

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

이 메서드를 이용해서 모든 조합의 info 문자열을 만들어준다

개발 언어, 직군, 경력, 음식, 점수

순으로 되어 있으니까 문자열을 만드는 count는 4번이다 (점수는 value로 저장하니까)

그래서 다음 문자열을 "-"로 붙일지 그냥 배열의 문자열로 붙일지를 재귀 호출로 구현한 것이다

 

 

2) 이분탐색

private static int binarySearch(String key, int score) {
        List<Integer> list = map.get(key);
        int start=0;
        int end = list.size()-1;
        while(start<=end) {
            int mid = (start+end)/2;
            if(list.get(mid) < score) {
                start = mid+1;
            } else {
                end = mid-1;
            }
        }
        return list.size()-start;
}

요건 입력받은 문자열을 key로 하는 점수 list를 불러다가 이분탐색 하는 메소드이다

음 그냥 말그대로 이분탐색하고 찾으면 그 위치부터 뒤에까지 몇개가 있는지 반환하면 몇명인지 구할 수 있다

이 때 이분탐색을 하려면 map의 value로 저장된 점수 list가 오름차순으로 정렬되어 있어야 한다

그래서 map에 모든 저장을 끝내고 오름차순을 해주는 로직을 추가해준다!

 

 

 

 

자바 코드)

package programmers;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class SearchRanking {
    static Map<String, List<Integer>> map;
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        map = new HashMap<>();

        for(int i=0;i<info.length;i++) {
            String[] arr = info[i].split(" ");
            // 가능한 모든 조합의 문자열을 map의 key 값으로 저장
            makeSentence(arr, "", 0);
        }

        // 문자열 별 점수 리스트를 오름차순으로 정렬한다
        for(String key : map.keySet()) {
            Collections.sort(map.get(key));
        }

        for(int i=0;i<query.length;i++) {
            int count = 0; // 만족하는 인원 수
            String[] arr = query[i].split(" ");
            // - and - and - and chicken 100
            int score = Integer.parseInt(arr[7]);
            StringBuilder sb = new StringBuilder();
            sb.append(arr[0]);
            sb.append(arr[2]);
            sb.append(arr[4]);
            sb.append(arr[6]);
            if(map.containsKey(sb.toString())) {
                count = binarySearch(sb.toString(), score);
            }
            answer[i] = count;
        }

        return answer;
    }

    private static int binarySearch(String key, int score) {
        List<Integer> list = map.get(key);
        int start=0;
        int end = list.size()-1;
        while(start<=end) {
            int mid = (start+end)/2;
            if(list.get(mid) < score) {
                start = mid+1;
            } else {
                end = mid-1;
            }
        }
        return list.size()-start;
    }

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

 

---

참고)

https://jisunshine.tistory.com/153

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