조합, 이분 탐색, HashMap

프로그래머스 2021 KAKAO BLIND RECRUITMENT Level 2 문제 순위 검색을 Java로 풀어보았다. 어지럽다. 씹..ㅏ
이게 왜 Level 2 냐고 미친놈들아!

문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/72412

---

지원자 정보 가능한 모든 조합 저장

사실 나는 지원자 정보인 info 쪽을 가지고 모든 조합을 구해야 한다는 생각도 처음에는 이해가 안됐다.

좀만 생각해보면 cpp, backend, senior, pizza는 곧 다음의 16 경우를 다 커버하는 것이다.
1. -, -, -, -
2. cpp, -, -, -
3. cpp, backend, -, -
4. cpp, -, senior, -
5. cpp, -, -, pizza
6. -, backend, senior, -
...
16. cpp, backend, senior, pizza

따라서 query가 하나 주어질 때 위와 같이 모든 조합을 다 저장해놔야 알맞게 매치가 될 수 있는 것이다.

아무리 텍스트로 써봤자 나도 못 알아먹을 것 같긴 하다. 혼자 그림 그려가면서 해보면 도움이 될 것이다.

어쨌든 info 배열을 돌며 모든 가능한 조합을 만들기 위해 다음과 같이 작성할 수 있다.

static HashMap<String, ArrayList<Integer>> applyMap = new HashMap<>();

for(String a: info){ // 가능한 모든 조합 만들기
     String[] apply = a.split(" ");
     combination(apply, "", 0);
}

                         ...

static void combination(String[] apply, String aCase, int cnt){
     if(cnt==4){
         if(!applyMap.containsKey(aCase)){
             ArrayList<Integer> tmp = new ArrayList<>();
             applyMap.put(aCase, tmp);
         }
         applyMap.get(aCase).add(Integer.parseInt(apply[4]));
         return;
     }
     combination(apply, aCase + "-", cnt+1);
     combination(apply, aCase + apply[cnt], cnt+1);
}

재귀를 통해서 가능한 모든 조합들을 만들어 낼 수 있다.

applyMap을 보면 HashMap<String, ArrayList<Intger>>의 형태인 걸 볼 수 있다. 특정 조합에 대해 나온 모든 점수들을 리스트로 value에 넣어준 것이다.

그런데 문제 조건을 보면 지원자 정보인 info 배열은 범위가 최대 5만이고, 합격 조건 정보인 query 배열은 범위가 최대 10만이다. 그럼 전수 조사를 하게 되면 최대 50억번의 조사가 필요할 수 있다. 오우 노우

따라서 모든 지원자를 다 볼 필요 없도록 만들어주기 위해 이분 탐색을 도입해야한다.

---

이분 탐색을 통한 지원자 선별

앞서 만든 모든 지원자의 조합들 정보를 저장한 applyMap의 value는 ArrayList<Integer>다.
이분 탐색을 이용하기 위해서는 이 ArrayList를 오름차순으로 정렬해줄 필요가 있다. 정렬을 하게 되면 query에서 받게 될 점수를 넘겨줘서 리스트의 어느 지점부터 시작해야 query 조건에 알맞은 지원자들을 뽑을 수 있는지 알 수 있다.

이것 역시 텍스트로만 쓰니까 ㅅㅂ 이해도 안 되고 말이 이상한 것 같다. 위 그림과 같이 생각하면 된다. applyMap의 특정 value가 위와 같은 5개의 원소를 가진 리스트고, 2번 인덱스부터 query의 점수보다 같거나 큰 지점이라면 총 2,3,4 번 3명이 뽑히게 되는 것이다.

이걸 코드로 표현하면 다음과 같다.

for(String key: applyMap.keySet()) // 가능한 조합들 각각의 점수 리스트를 오름차순 정렬하자
            Collections.sort(applyMap.get(key));

int idx = 0;
for(String q: query){ // 쿼리 배열 순회하며 가능한 조합들 applyMap에서 찾아주기
        q = q.replaceAll(" and ", "");
        String[] hire = q.split(" ");
        int score = Integer.parseInt(hire[1]);
        answer[idx++] = applyMap.containsKey(hire[0]) ? binarySearch(hire[0], score) : 0;
}

아래는 binarySearch 메소드 코드다.

static Integer binarySearch(String s, int score){
        ArrayList<Integer> cases = applyMap.get(s);
        int left = 0; int right = cases.size()-1;

        while(left<=right){
            int mid = (left+right)/2;

            if(cases.get(mid)<score)    left = mid + 1;
            else    right = mid - 1;
        }
        return cases.size() - left;
    }

---

머리가 종나 아프다. 띠바. 처음부터 최대 50억 번 돌아야 하는 걸 알았는데 이분 탐색은 생각하지도 못했다. 진짜 멀었다. 개빡친다. 알고리즘 씌바 ㅠㅠ... 문제 풀 때마다 너무 독립 시행이다 ㅠ...

오늘 배운 것

1. 탐색 횟수가 너무 많다 싶으면 이분 탐색을 한 번쯤 떠올려주자
2. 계속 조합 만드는 문제가 나온다. 상당히 최근 문제들이니까 조합, 순열 만드는 거 익혀놔야겠다...

---

2022.03.07 재시도 ( 실패 )

2차 시도로 다시 풀어봤는데 정확성 테스트까지는 다 맞혔는데 효율성 테스트가 다 시간초과가 났다. 결국 내 예전 풀이를 다시 봤는데 이분 탐색으로 알맞은 지원자를 찾지 못 한 게 주요했다.

또 지원자의 정보를 받고 지원자의 정보가 커버할 수 있는 모든 케이스를 탐색하지 않고, 합격 조건으로 제시된 query가 커버할 수 있는 모든 지원자의 정보를 HashMap에 저장한 것이 더 많은 메모리를 잡아먹게 된 요인이었던 것 같다. 물론 지원자 정보로 모든 조합을 만들었다 해도 이분 탐색으로 찾지 않았으면 어차피 시간 초과가 나긴 했을 것 같다.

효율성 테스트까지 만족해야 하는 문제는 어떻게 해야 덜 탐색을 할 수 있을지에 대해 고민할 수 있는 힘을 길러야 하는데, 아직까지는 그저 정확성 테스트 통과시키기는 데만 급급한 것 같다.

조금 더.. 완숙미가 넘치는 지경이 되기를 바라며.. 그동안 풀었던 문제들 계속해서 다시 시도해봐야겠다.