Programming프로그래머스경우의 수

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

,

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

문제 풀이

이 문제는 그냥 문자열대 문자열로 부딪히게 되면 시간 초과가 날 수 밖에 없는 문제다. 선형적으로 풀면 info 배열의 최대 크기는 5만, query 배열의 최대 크기는 10만 이므로 최대 50억 연산을 하게 되므로 효율성 측면에서 문제가 생긴다.
결국 이 문제는 어떤 방법을 이용해 검색할 것인가가 가장 큰 관건이 된다. 선형적인 탐색을 하는 방법이 아닌 O(logn)의 시간 복잡도를 갖는 자료구조 혹은 탐색 기법을 이용하는 방법으로 문제를 접근해야 한다. 동시에 만들 수 있는 문장의 경우의 수를 고려해줘야 한다. 복합적인 문제라 쉽지 않다.

처음에 각 문자열내 문자들을 파싱해서 map에다가 저장을 해야 하나?…. 그러면 탐색을 어떻게 해야하지?… 하면서 문제 접근을 못하다가 다른 분 풀이를 살짝 참고 했는데 문자열 자체를 map의 key값으로 넣는 것을 보고 힌트를 얻어 문제를 접근할 수 있었다.

  1. info 내 문자열을 정재해 띄어쓰기는 문장을 만들어준다.
  2. key로 정재된 문장을 value로는 같은 key를 갖는 문장에 대한 값들을 보관하기 위해 List형태로 넣어준다.
  3. info 내 문장들이 map으로 다 들어갔으면 Binary Search를 사용하기 위해 오름 차순으로 정렬 해준다.
  4. query 내 문자열을 정재해 준다.
    1. info에서 구분자는 띄어쓰기 였지만 query에서 구분자는 and와 띄어쓰기다.
    2. ‘-‘를 만나게 되면 만들 수 있는 문장의 모든 경우의 수를 만들어준다.
  5. 정재된 문자를 갖고 info에 값이 있는지 확인한다.
  6. 값이 있으면 List에서 query에서 요구하는 값 이상이 되는 사람 수를 찾는다.(Lower Bound)
    1. 쿼리가 여러개인 경우는 각각의 경우들을 모두 찾아서 더해준다.
  7. 찾은 결과를 answer에 넣어 반환한다.

info 내 문자열을 정재하기

public void infoToMap(String[] info) {
    for (int i = 0; i < info.length; i++) {
        String[] words = info[i].split(" ");
        StringBuilder sb = new StringBuilder();
        int score = Integer.parseInt(words[words.length - 1]);

        for (int j = 0; j < words.length - 1; j++) {
            sb.append(words[j]);
        }

        String key = sb.toString();
        infos.computeIfAbsent(key, k -> new ArrayList<>()).add(score);
    }
}

map 내 List값들을 오름차순으로 정렬하기

infos.forEach((key, value) -> {
    value.sort(null);
});

query 내 문자열 정재하고 모든 경우의 수 만들기

‘-‘는 모든 조건을 허용한다는 의미이므로 조건에 해당하는 모든 경우의 수를 만들어 주도록 한다.

String[] words = query[i].split(" and | ");

// 언어 cpp, java, python, -
// 직군 backend, frontend, -
// 경력 junior, senior, -
// 소울 푸드 chicken, pizza, -
// 점수
ArrayList<String> qu = new ArrayList<>();
qu.add("");

for (int j = 0; j < words.length - 1; j++) {

    int arrSize = qu.size();
    for (int aIndex = 0; aIndex < arrSize; aIndex++) {
        String subStr = qu.get(aIndex);

        if (words[j].equals("-")) {
            if (j == 0) {
                qu.set(aIndex, subStr + "cpp");
                qu.add(subStr + "java");
                qu.add(subStr + "python");
            } else if (j == 1) {
                qu.set(aIndex, subStr + "backend");
                qu.add(subStr + "frontend");
            } else if (j == 2) {
                qu.set(aIndex, subStr + "junior");
                qu.add(subStr + "senior");
            } else if (j == 3) {
                qu.set(aIndex, subStr + "chicken");
                qu.add(subStr + "pizza");

            }
        } else {
            qu.set(aIndex, subStr + words[j]);
        }
    }
}

정재된 query 문자열을 이용해 qeury에서 요구하는 값 이상의 사람 수를 찾는다.

public int binarySearch(List<Integer> list, int value) {
    int begin = 0;
    int end = list.size();
    int mid = (begin + end) / 2;

    while (begin < end) {
        mid = (begin + end) / 2;

        if (value > list.get(mid)) {
            begin = mid + 1;
        } else {
            end = mid;
        }
    }

    return list.size() - begin;
}
int num = 0;
for (int j = 0; j < qu.size(); j++) {
    String key = qu.get(j).trim();
    int value = Integer.parseInt(words[words.length - 1]);

    List<Integer> list = infos.getOrDefault(key, new ArrayList<>());
    num += binarySearch(list, value);
}
answer[i] = num;

전체 소스

import java.util.*;
import java.io.*;

class Solution {
    Map<String, List<Integer>> infos = new HashMap<>();
    // Map<String, Integer> querys = new HashMap<>();

    // int[] filter1()

    public int binarySearch(List<Integer> list, int value) {
        int begin = 0;
        int end = list.size();
        int mid = (begin + end) / 2;

        while (begin < end) {
            mid = (begin + end) / 2;

            if (value > list.get(mid)) {
                begin = mid + 1;
            } else {
                end = mid;
            }
        }

        return list.size() - begin;
    }

    public void infoToMap(String[] info) {
        for (int i = 0; i < info.length; i++) {
            String[] words = info[i].split(" ");
            StringBuilder sb = new StringBuilder();
            int score = Integer.parseInt(words[words.length - 1]);

            for (int j = 0; j < words.length - 1; j++) {
                sb.append(words[j]);
            }

            String key = sb.toString();
            infos.computeIfAbsent(key, k -> new ArrayList<>()).add(score);
        }

    }

    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];

        infoToMap(info);

        infos.forEach((key, value) -> {
            value.sort(null);
        });

        for (int i = 0; i < query.length; i++) {
            String[] words = query[i].split(" and | ");

            // 언어 cpp, java, python, -
            // 직군 backend, frontend, -
            // 경력 junior, senior, -
            // 소울 푸드 chicken, pizza, -
            // 점수
            ArrayList<String> qu = new ArrayList<>();
            qu.add("");

            for (int j = 0; j < words.length - 1; j++) {

                int arrSize = qu.size();
                for (int aIndex = 0; aIndex < arrSize; aIndex++) {
                    String subStr = qu.get(aIndex);

                    if (words[j].equals("-")) {
                        if (j == 0) {
                            qu.set(aIndex, subStr + "cpp");
                            qu.add(subStr + "java");
                            qu.add(subStr + "python");
                        } else if (j == 1) {
                            qu.set(aIndex, subStr + "backend");
                            qu.add(subStr + "frontend");
                        } else if (j == 2) {
                            qu.set(aIndex, subStr + "junior");
                            qu.add(subStr + "senior");
                        } else if (j == 3) {
                            qu.set(aIndex, subStr + "chicken");
                            qu.add(subStr + "pizza");

                        }
                    } else {
                        qu.set(aIndex, subStr + words[j]);
                    }
                }
            }

            int num = 0;
            for (int j = 0; j < qu.size(); j++) {
                String key = qu.get(j).trim();
                int value = Integer.parseInt(words[words.length - 1]);

                List<Integer> list = infos.getOrDefault(key, new ArrayList<>());
                num += binarySearch(list, value);
            }
            answer[i] = num;
        }
        return answer;
    }
}
Share