Algorithm/Binary Search

[프로그래머스 / python / Level 2] 순위 검색

양선규 2025. 6. 5. 15:26
728x90
반응형

문제

 

2021 KAKAO BLIND RECRUITMENT 출제 문제이다. Level 2이긴 한데 왜 2인지 전혀 모르겠고, 내가 느끼기엔 최소 Level 3이고 백준으로 치면 골드 4이상이 아닌가 싶다. 그냥 개인적 느낌이다.

 

단순 이분탐색만 사용되는 것이 아니라 해시, 조합, 문자열 파싱 등 다양한 알고리즘이 활용되고 구현요소도 많아서 실수할 부분이 매우 많고 복잡하다. 카카오 문제는 다 이런 거 같다. 하나의 알고리즘만 보는 게 아닌 이런저런 알고리즘을 조합하여 구현처럼 만들어내는 것.. 특히 초보자들에겐 더욱 어려운 것 같다. 나에게도 어렵고.

 

from collections import defaultdict
from itertools import product
import bisect

def solution(info, query):
    
    def get_all_combinations(conditions):
        """
        무관('-')을 포함한 2^4(16)개의 조합을 만듭니다.
        """
        choices = []
        for condition in conditions:
            choices.append([condition, '-'])
        
        # 16개 조합 리턴
        return list(product(*choices))
    
    def parse_query(q):
        """
        쿼리를 조건과 코테점수로 나누어 리턴합니다.
        """
        parts = q.replace(' and ', ' ').split()
        conditions = tuple(parts[:4])
        target_score = int(parts[-1])
        
        return conditions, target_score
    
    def binary_search(scores, target):
        """
        이분 탐색
        scores 리스트에서 target 이상인 요소의 개수를 리턴합니다.
        """
        idx = bisect.bisect_left(scores, target)
        return len(scores) - idx
        
    
    """모든 쿼리 경우의 수를 key로 가지고, 점수 리스트를 value로 매핑하는 딕셔너리"""
    score_dict = defaultdict(list)
    
    """
    모든 지원자 데이터 전처리
    "-"(무관) 데이터를 포함한 모든 경우의 수를 key로 하는 딕셔너리 생성
    value엔 key조건에 해당하는 지원자의 점수 리스트 할당
    """
    for person in info:
        parts = person.split()
        conditions = parts[:4]
        score = int(parts[-1])
        
        # 생성되거나/존재하는 모든 key에 점수 추가
        for combination in get_all_combinations(conditions):
            score_dict[combination].append(score)
    
    """이분 탐색을 위한 점수 리스트 정렬"""
    for key in score_dict:
        score_dict[key].sort()
        
    """메인 로직"""
    result = []
    
    for q in query:
        
        # 쿼리 파싱
        conditions, target_score = parse_query(q)
        
        # 쿼리에 맞는 점수 리스트 가져오기
        scores = score_dict[conditions]
        
        # 이분 탐색으로 target_score 이상인 개수 구하기
        count = binary_search(scores, target_score)
        result.append(count)
        
    return result

 

처음에 문제를 읽고 트리 자료구조와 재귀함수를 이용한 접근법을 떠올렸지만, 구현이 너무 복잡해 져서 포기했다. 그래도 데이터를 미리 분류해 두는 접근방법 자체는 일치했으니 그걸로 만족한다.

 

우선 이 문제는, 모든 쿼리에 대해 모든 지원자를 일일이 검토하면 시간 초과가 나온다. 단순하게 계산하여 지원자(50000) * 쿼리(100000) 만 해봐도 바로 50억이 떠버린다. 단순 완전탐색으로는 해결할 수 없다.

 

이 문제는 데이터 전처리가 중요하다. 마치 dp 테이블을 만드는 것 처럼 딕셔너리에 미리 데이터를 분류해 둔다.

각 조건(언어, 직무, 경력, 소울푸드)에 무관('-') 까지 포함해 가능한 모든 조합을 만들게 되면, 총 108개의 키를 가진 딕셔너리가 완성된다. 그리고 해당 key의 value로는, 그 조건에 해당하는 지원자들의 코테 점수를 리스트로 저장해둔다. 이러면 해시 테이블 특성 상 데이터에 key로 접근할 수 있게 되어, O(1) 상수 시간에 query에 대한 코테 점수 리스트를 얻을 수 있게 된다. 물론 전처리 단계 자체는 O(N) 이긴 하다.

 

그러나 코테 점수 리스트를 얻었다고 해도, 점수를 만족하는 지원자를 찾기 위해서 완전탐색을 하게 되면 또 시간초과가 난다. 예를 들어 모든 조건이 무관인 쿼리가 있다고 하면, 모든 사용자의 코테 점수(50000개)를 전부 탐색해야 한다. 이런 쿼리가 100000개 라면? 50000 * 100000 = 50억 으로 데이터 전처리를 한 것이 의미없게 되고 시간초과가 난다.

 

따라서 코테 점수 조건을 확인할 땐 이분 탐색을 해야 한다.

Q: 10만 (쿼리 수)

N: 5만 (지원자 수)

라고 할 때:

시간 복잡도는 O(Q * N) -> O(QlogN) 로 개선되고,

연산 횟수는 50억 -> 160만번 정도로 줄어들게 된다.

728x90
반응형