[프로그래머스, 자바] 순위검색 (2021 kakao blind recruitment)

프로그래머스 2단계 2021 카카오 순위검색

url: https://programmers.co.kr/learn/courses/30/lessons/72412?language=java

 

이 문제는 정확성과 효율성을 모두 평가한다. 그렇기 때문에 효울성을 통과하는 것이 가장 중요하며 어렵다.

처음에는 아래와 같이 문제를 풀었다.

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public int[] solution(final String[] info, final String[] query) {
        final List<Info> infos = Arrays.stream(info)
                                       .map(this::createInfo)
                                       .collect(Collectors.toList());
        final List<Info> queries = Arrays.stream(query)
                                         .map(this::createQuery)
                                         .collect(Collectors.toList());

        int index = 0;
        final int[] answer = new int[queries.size()];
        for (final Info q : queries) {
            answer[index++] = (int) infos.stream()
                                         .filter(i -> i.getScore() >= q.getScore())
                                         .filter(i -> i.isMatch(q))
                                         .count();
        }

        return answer;
    }

    private Info createInfo(final String s) {
        final String[] split = s.split(" ");
        return new Info(split[0], split[1], split[2], split[3], Integer.parseInt(split[4]));
    }

    private Info createQuery(final String s) {
        final String[] split = s.replaceAll(" and ", " ").split(" ");
        return new Info(split[0], split[1], split[2], split[3], Integer.parseInt(split[4]));
    }

    private static class Info {
        private String language;
        private String job;
        private String career;
        private String food;
        private int score;

        public Info(final String language, final String job, final String career, final String food, final int score) {
            this.language = language;
            this.job = job;
            this.career = career;
            this.food = food;
            this.score = score;
        }

        public boolean isMatch(final Info query) {
            if(!"-".equals(query.language) && !this.language.equals(query.language)) {
                return false;
            }

            if(!"-".equals(query.job) && !this.job.equals(query.job)) {
                return false;
            }

            if(!"-".equals(query.career) && !this.career.equals(query.career)) {
                return false;
            }

            if(!"-".equals(query.food) && !this.food.equals(query.food)) {
                return false;
            }

            return true;
        }

        public int getScore() {
            return score;
        }
    }

}

결과는 정확성 테스트는 모두 통과했지만, 효율성 테스트는 시간초과로 실패했다. 그럴듯하게 풀었지만 시간복잡도가 O(n^2) 이다. 

그래서 아래와 같이 풀이를 변경했다.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] solution(final String[] info, final String[] query) {
        final Map<String, int[]> infos = new HashMap<>();
        for (final String s : info) {
            addAllCaseInfo(s, infos);
        }

        final int[] answer = new int[query.length];
        for (int index = 0; index < answer.length; index++) {
            final String[] split = query[index].replaceAll(" and ", "").split(" ");
            final int[] infoScore = infos.get(split[0]);
            if(infoScore == null) {
                answer[index] = 0;
            }

            if(infoScore != null) {
                for (int i = Integer.parseInt(split[1]); i < infoScore.length; i++) {
                    answer[index] += infoScore[i];
                }
            }
        }

        return answer;
    }

    private void addAllCaseInfo(final String s, final Map<String, int[]> infos) {
        final String[] split = s.split(" ");
        for (String language : new String[]{split[0], "-"}) {
            for (String job : new String[]{split[1], "-"}) {
                for (String career : new String[]{split[2], "-"}) {
                    for (String food : new String[]{split[3], "-"}) {
                        final String info = language + job + career + food;
                        final int score = Integer.parseInt(split[4]);
                        if(infos.containsKey(info)) {
                            infos.get(info)[score]++;
                        } else {
                            final int[] arr = new int[100001];
                            arr[score]++;
                            infos.put(info, arr);
                        }
                    }
                }
            }
        }
    }

}

이번에는 Map 을 이용해서 시간복잡도를 줄였다. 이 문제는 아래와 같은 절차로 진행이 된다.

1. 지원자들의 정보들에 일치되는 모든 종류의 쿼리를 생성한다. ('-' 를 포함한 모든 종류의 쿼리) (경우의수 2^4)

2. Map<쿼리, 지원자 점수 배열> 자료 구조에 지원자들에 정보에 맞는 쿼리와 점수를 넣는다.

3. 지원자 점수 배열은 최대점수에 해당하게 크기를 잡는다

4. 점수가 30점이면, 30번째 인덱스에 1을 더한다. 결국은 30번째 인덱스는 30점을 가진 지원자의 수가 된다.

5. "java and backend and junior and pizza 100" 쿼리 같은 경우 Map 에서 "javabackendjuniorpizza" 키의 배열을 가져오고 100 ~ 100000 인덱스까지의 값들을 모두 더한값을 리턴하면 된다.

 

대부분 이 문제를 풀때 점수를 탐색하는 시간복잡도를 줄이기 위해 이진검색을 많이 사용한다고 한다.

하지만 나는 이 방법이 더 효율적인 방법이라고 생각한다. (절대 이진탐색 구현 방법을 잊어서가 맞다)

이유는 이진탐색을 사용하기 위해서는 값들을 정렬해야한다. 정렬을 위해서는 시간복잡도가 nlogn 이 소요된다.

그러나 이 방법은 n번만의 탐색이 가능하기 때문에 이 방법이 더 효율적이라고 생각한다. 

 

알고리즘을 정말 3천년만에 풀어본다. 매일 조금씩 문제를 풀어서... 뇌를 따뜻하게 만들어야 겠다.