[Java] 프로그래머스 - 순위 검색 (2단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	O
본인의 실력으로 풀었는가?	X

 

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

 

 

 

 

 

import java.util.*;
class Solution {
    //만들어지는 글자, 점수
    HashMap<String, ArrayList<Integer>> table;
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        table = new HashMap<>();
        
        //info 글자대로 만들 수 있는 조건 만들고, 해당 조건에 대해 점수 넣기
        for (int i = 0; i < info.length; i++) {
            String[] temp = info[i].split(" ");
            func(temp, 0, new StringBuilder());
        }
        
        //점수 오름차순 정렬
        for (String key : table.keySet()) {
            ArrayList<Integer> arr = table.get(key);
            Collections.sort(arr);
            table.put(key, arr);
        }
        
        //query에 맞는 것 보내기
        for (int i = 0; i < query.length; i++) {
            String[] temp = query[i].split(" ");
            StringBuilder sb = new StringBuilder(temp[0]);
            sb.append(temp[2]);
            sb.append(temp[4]);
            sb.append(temp[6]);
            
            //점수에 대해 이분탐색 하기
            ArrayList<Integer> arr = table.getOrDefault(sb.toString(), new ArrayList<>());
            int num = Integer.parseInt(temp[7]);
            int start = 0;
            int end = arr.size();
            
            while (start < end) {
                int mid = (start + end) / 2;
                if (arr.get(mid) >= num) {
                    end = mid;
                } else {
                    start = mid + 1;
                }
            }
            answer[i] = arr.size() - start;
        }
        return answer;
    }
    
    public void func(String[] l, int n, StringBuilder sb) {
        if (n == l.length - 1) {
            String str = sb.toString();
            ArrayList<Integer> p = table.getOrDefault(str, new ArrayList<>());
            p.add(Integer.parseInt(l[4]));
            table.put(str, p);
            return;
        }
        
        StringBuilder sb1 = new StringBuilder(sb);
        StringBuilder sb2 = new StringBuilder(sb);
        sb1.append(l[n]);
        sb2.append("-");
        func(l, n+1, sb1);
        func(l, n+1, sb2);
    }
}

 

정확성 테스트

테스트 1 〉	통과 (2.50ms, 75.1MB)
테스트 2 〉	통과 (2.93ms, 74.5MB)
테스트 3 〉	통과 (3.69ms, 72.3MB)
테스트 4 〉	통과 (5.68ms, 75.7MB)
테스트 5 〉	통과 (15.40ms, 86.1MB)
테스트 6 〉	통과 (20.76ms, 88.8MB)
테스트 7 〉	통과 (11.52ms, 79.7MB)
테스트 8 〉	통과 (82.82ms, 114MB)
테스트 9 〉	통과 (68.95ms, 115MB)
테스트 10 〉	통과 (70.68ms, 124MB)
테스트 11 〉	통과 (10.59ms, 85.4MB)
테스트 12 〉	통과 (16.07ms, 88.1MB)
테스트 13 〉	통과 (9.28ms, 90.9MB)
테스트 14 〉	통과 (44.65ms, 102MB)
테스트 15 〉	통과 (44.39ms, 94.3MB)
테스트 16 〉	통과 (9.43ms, 80.6MB)
테스트 17 〉	통과 (17.25ms, 89.3MB)
테스트 18 〉	통과 (38.10ms, 104MB)

효율성 테스트

테스트 1 〉	통과 (1188.39ms, 235MB)
테스트 2 〉	통과 (1068.00ms, 260MB)
테스트 3 〉	통과 (1108.71ms, 245MB)
테스트 4 〉	통과 (1163.31ms, 243MB)