[프로그래머스 lv.2 - 72412번] 순위 검색 // Java Map, Regex, BinarySearch 활용

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

프로그래머스

lv.1 어지간한 문제를 다 풀고 lv2로 넘어왔다.

lv.2의 가장 어려운문제들은 어떤지 궁금해서 마지막페이지로 가서 아무거나 누른 문제.

2021 카카오 코테 문제였나보다.

구현도 쉽지 않았지만, 계속 효율성테스트를 실패해서 약 4시간을 고민한 결과 문제를 잘못읽었음을 깨달았다.

query에 들어오는 조건이 순서가 뒤죽박죽일 수  있는줄 알았는데, 순서가 정해져있었다.

결론 : 문제가 길어도 똑바로 읽고 시작하자

 

<두번째 try>

기존 코드 문제 : 쿼리가 어떤 순서로 들어오는지 모른다고 생각을 해서, 쿼리를 split으로 나누고, 각 조건마다 for문을 돌면서 info가 그 조건을 contain하는지 확인했다. 또한, 이 작업을 info의 모든 element에 대해 해야해서 시간이 굉장히 많이 걸렸다.

추가적으로, 문제에 info는 최대 10만, query는 최대 50만의 길이로 위 코드의 이중포문은 최대 50억번을 돌게된다.😂

 

개선방안 : 언어,직군,경력,소울푸드를 구분할 수 있는 key를 만들어서 Map의 key로 사용하고, 해당 key의 value는 List로 선언을 해서, 해당key를 가진 지원자들의 점수를 삽입해주도록 한다.

==> 이렇게 하면 Map.get(key)를 통해 조건들에 해당하는 지원자들의 점수리스트를 가져오고, reverse sort 후 indexOf로 해당 점수를 넘은 사람이 몇명인지 알아낼 수 있을 듯.

 

생각해볼 점 : info에는 모든 정보가 있지만, query에는 누락된 조건이 있을 수 있다.

예를 들어, info상의 "java backend junior pizza" 지원자는 query의 "java and - and - and - 150" 조건에 의해 검색되어야한다. 두 개의 다른 string을 어떻게 같은 조건으로 검색할것인지(Map의 key를 찾을 때 정규표현식을 쓸수있나 ?)

 

<세 번째 Try>

글쓰다가 뒤로가기 눌러서 코드 캡쳐가 사라졌다 ....

 

각 조건마다 1~9의 숫자 string을 주어 조건들의 조합으로 key를 생성하였다.

<info 인코딩>

java backend senior pizza 150 ==> encode_query와 getScore 함수에서 각각

"3579"의 key와 int 150의 숫자로 인코딩하였다.

이처럼 만들어진 (3*2*2*2) = 24개의 key와, ArrayList를 가진 Map을 선언하여

각각의 key에 해당하는 지원자들의 점수를 삽입한뒤, 추후에 있을 탐색을 위해 정렬해두었다.

keyMap :    Map< String, List<Integer>>

 

<query 인코딩>

query도 마찬가지로 인코딩해주었는데, query의 경우 조건이 주어지지 않는 항목들이 있어 정규식으로 처리해주었다.

"- and backend and - and pizza 150"와 같은 query에서 and와 pizza를 지우고, split()의 regex를 "\s+"로 주어 하나 이상의 공백을 기준으로 split하였다. 

"- and backend and - and pizza"  ==> key  : "59"  score : 150

"- and - and - and - 150"              ==> key : ""      score : 150

 

<keySet 검색>

처리된 query string의 각 문자들을 모두 포함하고 있는 key들을 검색하여, 이들 각각의 리스트에서 점수로 걸러내면 정답을 얻을 수 있다고 생각했다.

- Map.keySet()의 각 원소(key)가 contains(Regex)인지 검사한다.

- Regex = "(?=.*" + String.join(")(?=.*", qr.split("")) + ").*"   ==> key가 query의 각 char을 적어도 하나 포함하는지

 

<List 검색>

regex로 얻은 key들의 List를 각각 가져오고, 각 리스트에서 >점수컷 인 사람을 세서 answer에 누적시킨다.

 

<결과분석>

효율성 테스트를 4개 중 2개 통과했다. 이 문제에서 가장 시간이 오래 걸리는 부분은 각 query에 대해서 List를 탐색하는 부분일 것이다. 내가 한 방법대로 하면 쿼리 조건이 빈 것 없이 4개를 채워서 들어오면 탐색을 한 번만 하지만, 

- - - - 150 처럼 점수만 조건으로 들어왔을때는 최대 (3*2*2*2) = 24번의 탐색을 진행하게 된다. 이게 효율성테스트를 통과하지 못하는 직접적인 이유인 듯하다.

 

<다른방법>

조건에 빈 틈이 있어도 탐색횟수를 줄이려면, 빈 조건이 있는 조건까지 key를 생성해주면 된다. 기존 (3*2*2*2)의 key에서 조건이 빠지는 경우까지 생각하여 (4*3*3*3) = 108개의 고유  key를 생성하고, info의 조건 하나마다 포함,불포함하는 경우 총 16가지의 경우의 수에 점수를 모두 삽입해주면 된다.

문제를 보자마자 생각했던 방법인데, 당시에는 "조건 영역의 개수가 늘어나거나, 조건의 option이 한두가지만 추가되어도, 하나의 info에 대해 삽입해야할 Key의 permutation이 기하급수적으로 많아지기 때문에 리소스 측면에서 낭비가 심하다" 라고 생각했다. 내가 간과한 것은 query의 개수가 많으면 많을수록 HashTable을 만드는 것에 대한 기회비용이 작아진다는 것이다. (한 번 잘 만들어놓으면 매 query에 대해 단 한 번의 탐색만 하도록 보장해줄 수 있기 때문)

내가 풀었던 방법은 삽입의 비용이 이걸 상쇄할정도로 매우 크거나, query들의 조건이 빠짐없이 전달된다고 가정했을 때 효과적일 것이라고 생각한다.

 

<최종 풀이>

 

import java.util.*;
class Solution {
    public static int[] solution(String[] info, String[] query) {
        //initialize codeMap
        codeMap.put("cpp",'1'); codeMap.put("java",'2'); codeMap.put("python",'3');
        codeMap.put("frontend",'4'); codeMap.put("backend",'5'); codeMap.put("senior",'6');
        codeMap.put("junior",'7'); codeMap.put("chicken",'8'); codeMap.put("pizza",'9'); codeMap.put("-",'-');
        int[] answer = new int[query.length];
        //Map 생성, key permutation별로 전부 삽입해주기
        Map<String, List<Integer>> keyMap = new HashMap<>();
        for (String inf:info){
            int score = getScore(inf);
            String[] encoded = encode_info(inf);
            for (String key:encoded){
                if (!keyMap.containsKey(key)){
                    keyMap.put(key, new ArrayList<Integer>());
                }
                keyMap.get(key).add(score);
            }
        }
        ///key별로 미리 정렬해놓기
        for (String elem:keyMap.keySet()){
            Collections.sort(keyMap.get(elem));
        }
        //query를 돌면서 이분탐색 진행
        int ansidx = 0;
        for (String qr:query){
            int cut = getScore(qr);
            qr = encode_query(qr);
            if (keyMap.containsKey(qr)){
                List<Integer> lst = keyMap.get(qr);
                answer[ansidx] = countscore(lst, cut);
                ansidx++;
            }
            else{
                answer[ansidx] = 0;
                ansidx++;
            }
        }
        return answer;
    }

    public static Map<String, Character> codeMap = new HashMap<>();

    public static char stringTocode(String code){

        return codeMap.get(code);
    }

    public static String[] encode_info(String info){

        String[] tempsplit = info.replaceAll(" [0-9]+", "").split(" ");
        int idx = 0;
        String[] permutations = new String[16];
        for (int i = 0; i<2; i++){
            char[] encoded = new char[4];
            encoded[0] = (i == 1)?stringTocode(tempsplit[0]):'-';
            for(int j = 0; j<2; j++){
                encoded[1] = (j == 1)?stringTocode(tempsplit[1]):'-';
                for(int k = 0; k < 2; k++){
                    encoded[2] = (k == 1)?stringTocode(tempsplit[2]):'-';
                    for(int n = 0; n<2; n++){
                        encoded[3] = (n == 1)?stringTocode(tempsplit[3]):'-';
                        permutations[idx] = String.valueOf(encoded);
                        idx++;
                    }
                }
            }
        }
        return permutations;
    }

    public static String encode_query(String query){
        String encoded = "";
        String[] tempsplit = query.replaceAll(" [0-9]+","").split(" and ");
        for (String sp:tempsplit){
            encoded += stringTocode(sp);
        }
        return encoded;
    }

    public static int getScore(String info){
        return Integer.parseInt(info.replaceAll("[^0-9*]",""));
    }

   public static int countscore(List<Integer> arr, int score){

    int mid=0;
    int end = arr.size();
    int start = 0;

    while (end > start) // end가 start보다 같거나 작아지면, 그 값이 Lower Bound이므로 반복을 종료한다.
    {
        mid = (start + end) / 2; 
            if (arr.get(mid) >= score) // 중간값이 원하는 값보다 크거나 같을 경우, 끝값을 중간값으로 설정하여 다시 탐색한다.
            end = mid;
        else start = mid + 1; // 중간값이 원하는 값보다 작을 경우, 시작값을 중간값+1로 설정하여 다시 탐색한다.
    }
    return arr.size()-start;

    }
}

조건들을 숫자로 mapping해줄 필요는 없지만, regex 연습할 겸 사용해봤다.

자바의 객체지향에 익숙해지면 리팩토링 해봐야겠다.

 

 

<배운 점>

1. 문제를 잘 읽어야된다

2. 풀이를 구상할 때, 연산량이 큰 메서드가 무엇인지 생각하고, 요구조건에 맞게 설계해야한다(중요)

3. 여러번 풀면서 문자열을 다르게 처리하며 정규표현식 쓰는 연습 해봄 --> 글 따로 정리

4. Map의 Entry element를 List로 하여 저장하는 아이디어