(Java) 프로그래머스 - 순위 검색

카카오 문제답게 어려운 문제였다.

정확성은 통과하기 쉬웠으나 효율성을 통과하긴 어려웠다.

점수 배점이 정확성에 40점 효율성에 60점이니

효율성을 통과하지 못하면 0.5솔도 못하는 것이다.

 

처음에는 info와 query 배열로 들어온 정보들을 인스턴스로 만들어 하나씩 비교하려고 했다.

info값이 50,000 이하, query값이 100,000 이하니 선형 탐색으로 둘을 비교할 시 시간 초과가 날것을 예상했지만

다른 방법이 떠오르지 않아 선형 탐색으로 풀었다.

인스턴스를 150,000개나 만들어 중첩 if문으로 탐색하는 코드를 만드니 메모리가 초과될 수도 있고... 

애당초 비교를 위해서 인스턴스를 만드는게 아닌 것 같다는 생각을 했다.

메모리 초과는 일어나지 않았지만 효율성에서 통과하지 못했고 다른 방법을 생각해 보았다.

 

한참 생각하다 이진 탐색이 떠올랐다. 그러나 이진 탐색을 하려면 정렬되어 있어야 하는데

어떤 기준으로 정렬해야 할지 고민이 되었고 점수순으로 정렬을 해야 한다는 결론이 났다.

그러나 문자열과 숫자를 분리해서 어떻게 저장해야 할지 모르겠어서 검색을 통해 힌트를 얻었다.

키포안트는 문자열의 모든 조합의 HashMap 만드는 것이었다.

모든 조합의 HashMap은 전혀 생각하지 못했던 방식이었고 거기에 조합이 더해지니 문제를 풀 수 있겠다 생각이 들었다.

다만 여전히 조합을 만드는 메서드가 좀 어려웠고 다른 부분은 그리 어렵지 않았다.

이진 탐색을 코드로 구현하는 건 처음이었는데 앞으로 자주 사용할 것 같은 느낌이다.

---

최초 코드(효율성 실패)

package progammers;

import java.util.Arrays;
import java.util.StringTokenizer;

public class RankSearch_L2 {
    public static void main(String[] args) {
        String[] info = {"java backend junior pizza 150", "python frontend senior chicken 210", "python frontend senior chicken 150", "cpp backend senior pizza 260", "java backend junior chicken 80", "python backend senior chicken 50"};
        String[] query = {"java and backend and junior and pizza 100", "python and frontend and senior and chicken 200", "cpp and - and senior and pizza 250", "- and backend and senior and - 150", "- and - and - and chicken 100", "- and - and - and - 150"};
        int[] answer = new int[query.length];

        Volunteer[] volunteer = new Volunteer[info.length];
        for (int i = 0; i < info.length; i++) {
            StringTokenizer st = new StringTokenizer(info[i]);
            volunteer[i] = new Volunteer(st.nextToken(), st.nextToken(), st.nextToken(), st.nextToken(), Integer.parseInt(st.nextToken()));
        }

        Query[] queries = new Query[query.length];
        for (int i = 0; i < query.length; i++) {
            query[i] = query[i].replaceAll("( and )", " ");
            StringTokenizer st = new StringTokenizer(query[i]);
            queries[i] = new Query(st.nextToken(), st.nextToken(), st.nextToken(), st.nextToken(), Integer.parseInt(st.nextToken()));
        }

        for (int i = 0; i < queries.length; i++) {
            int cnt = 0;
            String l = queries[i].getLanguage();
            String p = queries[i].getPosition();
            String t = queries[i].getType();
            String f = queries[i].getFavorite();
            int s = queries[i].getScore();
            for (Volunteer value : volunteer) {
                String vl = value.getLanguage();
                String vp = value.getPosition();
                String vt = value.getType();
                String vf = value.getFavorite();
                int vs = value.getScore();

                if (l.equals(vl) || l.equals("-")) {
                    if (p.equals(vp) || p.equals("-")) {
                        if (t.equals(vt) || t.equals("-")) {
                            if (f.equals(vf) || f.equals("-")) {
                                if (vs >= s) {
                                    cnt++;
                                }
                            }
                        }
                    }
                }
                answer[i] = cnt;
            }
        }
        System.out.println(Arrays.toString(answer));
    }
}

class Volunteer {
    public String getLanguage() {
        return language;
    }

    public String getPosition() {
        return position;
    }

    public String getType() {
        return type;
    }

    public String getFavorite() {
        return favorite;
    }

    public int getScore() {
        return score;
    }

    String language;
    String position;
    String type;
    String favorite;
    int score;

    Volunteer(String l, String p, String t, String f, int s) {
        this.language = l;
        this.position = p;
        this.type = t;
        this.favorite = f;
        this.score = s;
    }
}

class Query {
    public String getLanguage() {
        return language;
    }

    public String getPosition() {
        return position;
    }

    public String getType() {
        return type;
    }

    public String getFavorite() {
        return favorite;
    }

    public int getScore() {
        return score;
    }

    String language;
    String position;
    String type;
    String favorite;
    int score;

    Query(String l, String p, String t, String f, int s) {
        this.language = l;
        this.position = p;
        this.type = t;
        this.favorite = f;
        this.score = s;
    }
}

 

최종 코드

import java.util.*;
class Solution {
    static HashMap<String, ArrayList<Integer>> hm;
    public int[] solution(String[] info, String[] query) {
                int[] answer = new int[query.length];

        // 문자열과 점수를 담을 HashMap
        hm = new HashMap<>();

        // info로 모든 조합 만들기
        for (int i = 0; i < info.length; i++) {
            String[] infoTemp = info[i].split(" ");
            combination(infoTemp, "", 0);
        }

        // 이진 탐색을 위한 hm.values 정렬
        for (ArrayList<Integer> value : hm.values()) {
            Collections.sort(value);
        }

        // query 배열 수정
        for (int i = 0; i < query.length; i++) {
            query[i] = query[i].replaceAll(" (and) ", "");
            String[] queryTemp = query[i].split(" ");
            // 이진 탐색 후 answer 배열에 값 삽입
            answer[i] = hm.containsKey(queryTemp[0]) ? binarySearch(queryTemp[0], Integer.parseInt(queryTemp[1])) : 0;
        }

        return answer;
    }
    // 조합 메서드
    static void combination(String[] s, String str, int cnt) {
        // 조합이 완성되면
        if (cnt == 4) {
            // 완성된 str이 없다면
            if (!hm.containsKey(str)) {
                hm.put(str, new ArrayList<>());
            }
            // 있다면 list를 가져와서 점수 추가
            hm.get(str).add(Integer.parseInt(s[4]));
            return;
        }
        combination(s, str + "-", cnt + 1);
        combination(s, str + s[cnt], cnt + 1);
    }

    // 이진 탐색 메서드
    static int binarySearch(String key, int score) {
        ArrayList<Integer> list = hm.get(key);
        int left = 0;
        // list 인덱스는 0부터 시작하므로 -1
        int right = list.size() - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            // 중간값이 기준값보다 작으면
            if (list.get(mid) < score) {
                // 왼쪽을 버린다.
                left = mid + 1;
                // 그게 아니면 오른쪽을 버린다.
            } else {
                right = mid - 1;
            }
        }
        // left가 조건에 맞는 처음 인덱스이므로 list.size()에서 처음 인덱스 값을 빼기
        return list.size() - left;
    }
}