[2021 KAKAO Blind Recruitment] Q3. 순위 검색 (C++, Python, Java)

문제 링크

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

 

예상 난이도

S2 - G5

 

알고리즘 분류

이분 탐색 or Prefix Sum

 

풀이

직관적으로 떠오르는 풀이는 O(NM)이지만 이렇게 풀면 효율성을 통과할 수 없습니다. 풀이를 알아내기 위해 먼저 만약 모든 쿼리가 "- and - and - and -"였다면 어떻게 해결가능할지 생각해봅시다.

 

모든 쿼리가 "- and - and - and -"였다면 우리는 점수 목록만을 가지고 있다가 x점 이상인 사람의 수를 주면 되는데, 먼저 전처리 O(NlgN), 각 쿼리당 O(lgN)에 해결 가능한 정렬 및 이분 탐색 아이디어를 이해해봅시다.

 

먼저 전처리 과정에서는 점수목록을 한데 모았다가 먼저 정렬을 합니다. 

 

이후 각 쿼리에 대해서는 이렇게 이분 탐색을 하면 끝입니다.

 

그 다음으로 전처리 O(N), 각 쿼리당 O(1)에 해결 가능한 Prefix sum 아이디어를 이해해봅시다. 전처리 단계에서는 각 점수의 등장 횟수를 세어둡니다.

 

그 후 누적합을 취하면 일단 전처리는 끝납니다.

 

이렇게 전처리를 하고 나면 쿼리는 처리가 매우 쉬운데, Prefix Sum 테이블의 i번째 인덱스의 의미는 점수가 i점 이하인 사람의 수입니다. 그렇기에 x점 이상인 사람의 수를 구하고 싶으면 7(전체 사람 수) - Table[x]를 계산하면 끝입니다.

 

이분 탐색 혹은 Prefix Sum을 이용해 모든 쿼리가 - and - and - and - 를 해결하는 방법은 이해했습니다. 그런데 문제에서는 다양한 쿼리가 주어지는데 어떻게 해야할까요? 여기서는 각 쿼리 종류 108개에 대응되는 배열을 다 만들어둔 다음 info 배열의 원소를 여러 곳에 저장하는 아이디어를 떠올릴 수 있어야 합니다.

 

4차원 배열은 그리기가 애매하니 2차원으로만 예를 들어보면, 이렇게 java backend ... ... 20이 들어올 경우 (- -) (- backend) (java -) (java backend) 이 4곳에 20을 담아주면 됩니다.

 

설명은 생략합니다.

 

이렇게 처리를 다 끝내고 나면 쿼리가 들어올 때 마다 대응되는 배열만 보고 계산을 하면 끝입니다. 다른 사람의 코드를 보면 Python dictonary나 Java HashMap을 남용하는 경우를 볼 수 있었는데, 인덱스가 전부 작은 정수 범위 안에 들어올 경우 배열을 사용하면 되니 그러지 않도록 합시다.

 

시간복잡도의 상수 16은 각 info마다 최대 16군데의 배열에 값을 추가해줘야 하기 때문입니다. Prefix Sum의 경우 이론적인 시간복잡도는 더 좋으나 전처리 과정의 연산량이 더 많아 Prefix Sum이 이분 탐색보다 반드시 빠른건 아닙니다. 구체적으로 Prefix Sum에서는 대입이 아주 빈번하게 발생하기 때문에 대입연산이 느린 Python에서는 Prefix Sum이 아주 느리게 동작했습니다.

 

지금은 info를 처리할 때 여러 배열에 값을 담았는데, 반대로 info는 그냥 한 배열에 담고 query를 처리할 때 여러 배열을 보는 풀이도 떠올릴 수 있습니다. 이 풀이는 시간복잡도 상으로 더 비효율적이지만 시간 제한이 넉넉해서 통과 가능합니다.

 

마지막으로 Prefix Sum 풀이는 점수의 최댓값이 더 컸다면 사용이 불가능했습니다.

 

 

코드(C++, 이분 탐색)

 

사실 다른 것보다 문자열에 대한 처리가 껄끄러웠습니다. 문자열 처리만 빼면 의외로 코드가 그렇게 길지는 않습니다. index를 v[0]*27 + v[1]*9 + v[2]*3 + v[3]으로 계산했습니다. 이분 탐색을 직접 구현하는 대신 STL lower_bound를 써서 편하게 짰습니다.

 

코드(C++, Prefix Sum)

 

설명은 생략합니다.

 

코드(Python, 이분 탐색)

 

파이썬의 bisect 라이브러리를 이용해 이분 탐색을 쉽게 수행했습니다.

 

코드(Python, Prefix Sum)

 

코드(Java, 이분 탐색)

 

아쉽게도 자바에서는 이분 탐색을 직접 구현해야 합니다. mid = (st+en) / 2; 로 둬야하는지, (st+en+1) / 2로 둬야하는지 잘 생각하셔야 합니다.

 

코드(Java, Prefix Sum)

 

관련 강의

0x13강 - 이분탐색