문제 30 - 순위 검색 (Python)

프로그래머스

 

조건 4개와 점수 기준을 만족하는 지원자 수를 빠르게 구하는 문제입니다. 핵심은 조건 검색은 딕셔너리로 처리하고, 점수 기준 검색은 정렬된 리스트와 이진 탐색으로 처리하는 것입니다.

---

1.  나의 풀이

import bisect
from bisect import bisect_left
from copy import deepcopy
from itertools import product


def count_more(a, left_val):
    left_idx = bisect_left(a, left_val)
    return len(a) - left_idx


def solution(info, query):
    structure = dict({'backend':
                          dict({'junior':
                                    dict({'chicken': [], 'pizza': []})
                                   , 'senior':
                                    dict({'chicken': [], 'pizza': []})
                                })
                         , 'frontend':
                          dict({'junior':
                                    dict({'chicken': [], 'pizza': []})
                                   , 'senior':
                                    dict({'chicken': [], 'pizza': []})
                                })
                      })

    candidates = dict({'cpp': deepcopy(structure), 'java': deepcopy(structure), 'python': deepcopy(structure)})
    for info_text in info:
        q = list(info_text.split())
        bisect.insort(candidates[q[0]][q[1]][q[2]][q[3]], int(q[4]))

    answer = []
    for query_text in query:
        q = list(query_text.replace(' and ', ' ').split())
        q0 = ['cpp', 'java', 'python'] if q[0] == '-' else [q[0]]
        q1 = ['backend', 'frontend'] if q[1] == '-' else [q[1]]
        q2 = ['junior', 'senior'] if q[2] == '-' else [q[2]]
        q3 = ['chicken', 'pizza'] if q[3] == '-' else [q[3]]
        q4 = int(q[4])

        queries = list(product(q0, q1, q2, q3))
        total_num = 0
        for q in queries:
            total_num += count_more(candidates[q[0]][q[1]][q[2]][q[3]], q4)
        answer.append(total_num)
    return answer

지원자를 언어 → 직군 → 경력 → 음식 구조로 분류해 저장했습니다. 각 말단 리스트에는 점수만 저장하고, 쿼리에 -가 나오면 product로 가능한 조건 조합을 만들어 여러 리스트를 조회했습니다.

점수 조건은 bisect_left를 사용해 기준 점수 이상인 인원 수를 빠르게 계산했습니다.

def count_more(a, left_val):
    left_idx = bisect_left(a, left_val)
    return len(a) - left_idx

정렬된 점수 리스트에서 bisect_left(a, X)는 X 이상이 처음 시작되는 위치를 반환합니다. 따라서 전체 길이에서 해당 인덱스를 빼면 X점 이상인 사람 수가 됩니다.

---

2.  오늘 배운 점 및 복기 노트

조건 검색과 점수 검색 분리

이 문제는 조건 4개와 점수 기준을 한 번에 처리하려고 하면 복잡해집니다. 조건 검색은 딕셔너리 key로 처리하고, 점수 검색은 정렬된 리스트에서 이진 탐색으로 처리하는 식으로 역할을 나누는 것이 핵심입니다.

scores = candidates[lang][job][career][food]
answer = len(scores) - bisect_left(scores, score)

조건은 바로 찾아가고, 점수는 이진 탐색으로 개수를 세는 구조입니다.

---

bisect_left의 의미

bisect_left는 정렬된 리스트에서 특정 값이 들어갈 수 있는 가장 왼쪽 위치를 반환합니다.

scores = [50, 80, 150, 150, 210, 260]
idx = bisect_left(scores, 150)

위 코드에서 idx는 2입니다. 인덱스 2부터 끝까지가 150점 이상이므로 len(scores) - idx를 계산하면 됩니다.

이 문제에서는 정확히 같은 점수를 찾는 것이 아니라, 기준 점수 이상인 사람 수를 구해야 하므로 bisect_left가 적절합니다.

---

product를 사용한 이유

쿼리에 -가 들어오면 해당 조건은 고려하지 않는다는 뜻입니다.

예를 들어 다음 쿼리는 언어와 음식 조건을 고려하지 않습니다.

- and backend and senior and - 150

나의 풀이는 이 조건을 실제 가능한 조합으로 펼쳤습니다.

q0 = ['cpp', 'java', 'python'] if q[0] == '-' else [q[0]]
q1 = ['backend', 'frontend'] if q[1] == '-' else [q[1]]
q2 = ['junior', 'senior'] if q[2] == '-' else [q[2]]
q3 = ['chicken', 'pizza'] if q[3] == '-' else [q[3]]

queries = list(product(q0, q1, q2, q3))

product는 여러 리스트에서 가능한 모든 조합을 만들어줍니다. 이 문제에서는 -를 실제 조건 조합으로 바꾸는 데 사용했습니다.

---

개선할 수 있는 방향

나의 풀이는 쿼리에서 -를 만날 때마다 product로 여러 조합을 만들어 조회했습니다. 더 효율적인 방식은 지원자를 저장할 때부터 - 조건까지 함께 저장하는 것입니다.

예를 들어 다음 지원자가 있다고 하겠습니다.

java backend junior pizza 150

이 지원자는 정확한 조건뿐 아니라 아래 조건에도 해당합니다.

java backend junior pizza
- backend junior pizza
java - junior pizza
java backend - pizza
java backend junior -
...
- - - -

조건 4개가 각각 실제 값 또는 -가 될 수 있으므로 지원자 1명당 \( 2^4 = 16 \)개의 key에 점수를 저장할 수 있습니다.

그러면 쿼리에서 product를 만들 필요 없이, 쿼리 조건 그대로 딱 한 곳만 조회하면 됩니다.

for case in product([lang, '-'], [job, '-'], [career, '-'], [food, '-']):
    info_dict[case].append(score)

---

insort보다 append 후 정렬이 더 빠름

나의 풀이에서는 점수를 넣을 때 bisect.insort를 사용했습니다.

bisect.insort(candidates[q[0]][q[1]][q[2]][q[3]], int(q[4]))

insort는 삽입 위치를 찾는 것은 빠르지만, 리스트 중간에 값을 넣기 위해 뒤의 원소들을 밀어야 합니다. 따라서 실제 삽입 비용은 커질 수 있습니다.

이 문제에서는 점수를 넣을 때마다 정렬하지 말고, 일단 append로 모두 넣은 뒤 마지막에 각 점수 리스트를 한 번씩 정렬하는 방식이 더 적절합니다.

info_dict[case].append(score)

for key in info_dict:
    info_dict[key].sort()

---

쿼리 안에서 sorted()를 하면 시간 초과가 남

추가로 풀어본 코드에서는 쿼리마다 아래처럼 정렬을 수행했습니다.

answer.append(count_more(sorted(info_dict[tuple(q[:-1])]), int(q[4])))

이 방식은 시간 초과가 납니다. 쿼리가 최대 100,000개이므로 같은 리스트를 여러 번 다시 정렬할 수 있기 때문입니다.

정렬은 모든 지원자 정보를 저장한 뒤 한 번만 해야 합니다.

for key in info_dict:
    info_dict[key].sort()

그리고 쿼리 처리 중에는 이미 정렬된 리스트를 그대로 사용해야 합니다.

scores = info_dict[tuple(q[:-1])]
answer.append(count_more(scores, int(q[4])))

---

딕셔너리 컴프리헨션 구조

아래 코드는 가능한 모든 조건 조합을 key로 만들고, 각 key의 value를 빈 리스트로 초기화합니다.

info_dict = {
    i: []
    for i in list(product(languages, jobs, careers, foods))
}

딕셔너리 컴프리헨션은 다음 형태입니다.

{key: value for item in iterable}

따라서 위 코드는 product(languages, jobs, careers, foods)에서 나온 각 조합을 key로 사용하고, value로 빈 리스트를 넣는 코드입니다.

예를 들어 key는 다음과 같은 튜플이 됩니다.

('java', 'backend', 'junior', 'pizza')

---

3. 프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

입력 크기를 먼저 보고 완전탐색 가능 여부 판단하기

교재의 첫 풀이는 모든 쿼리마다 모든 지원자를 검사하는 방식입니다. 정확성은 통과할 수 있지만 효율성에서 실패합니다.

입력 크기를 보면 이유가 분명합니다.

info 최대 50,000
query 최대 100,000

단순 비교를 하면 최대 \( 50,000 \times 100,000 \)번 탐색하게 됩니다. 즉, 50억 번 수준의 반복이 발생합니다.

이 문제에서는 처음부터 완전탐색으로는 어렵다는 판단이 필요합니다.

---

데이터를 이진 탐색 가능한 형태로 바꾸기

이 문제에서 중요한 점은 이진 탐색을 바로 적용하는 것이 아닙니다. 이진 탐색을 사용할 수 있도록 데이터를 먼저 재구성해야 합니다.

교재에서는 조건 조합을 key로 만들고, 해당 조건에 속하는 지원자의 점수를 리스트로 모읍니다.

people[key].append(score)

그 후 점수 리스트를 정렬합니다.

for key in people:
    people[key].sort()

이렇게 만들어두면 쿼리마다 조건에 맞는 점수 리스트를 바로 찾고, bisect_left로 기준 점수 이상인 사람 수를 구할 수 있습니다.

---

- 조건은 전처리로 해결하기

쿼리에서 -를 만날 때마다 가능한 모든 경우를 탐색하면 쿼리 처리 비용이 커집니다.

교재의 핵심 아이디어는 지원자 한 명이 만족할 수 있는 모든 조건 패턴을 미리 만들어 저장하는 것입니다.

지원자 한 명의 조건이 4개이고, 각 조건은 실제 값 또는 -가 될 수 있으므로 총 16개의 경우가 만들어집니다.

정확한 조건 1개
조건 1개를 생략한 경우
조건 2개를 생략한 경우
조건 3개를 생략한 경우
조건 4개를 모두 생략한 경우

이렇게 저장해두면 쿼리는 조건 key 하나만 조회하면 됩니다.

---

combinations와 product의 차이

product는 여러 리스트에서 가능한 모든 조합을 만듭니다. 나의 풀이에서는 쿼리의 -를 실제 조건들로 펼칠 때 사용했습니다.

product(q0, q1, q2, q3)

combinations는 하나의 리스트에서 일부 원소를 고를 때 사용합니다. 교재에서는 지원자의 조건 중 일부만 선택해 key를 만드는 데 사용했습니다.

combinations(person, j)

정리하면 다음과 같습니다.

product: 여러 그룹에서 하나씩 골라 모든 조합 생성
combinations: 한 그룹 안에서 일부 원소 선택

---

문자열 key보다 tuple key가 더 안전함

교재에서는 조건을 문자열로 이어붙여 key를 만들었습니다.

people[''.join(person)].append(score)

이 문제에서는 조건 값들이 서로 명확히 구분되기 때문에 동작합니다. 하지만 일반적으로는 문자열을 그냥 붙이면 key 충돌이 생길 수 있습니다.

예를 들어 아래 두 경우는 모두 같은 문자열이 됩니다.

['ab', 'c']
['a', 'bc']

둘 다 붙이면 "abc"가 됩니다.

실전에서는 튜플 key를 쓰는 방식이 더 안전합니다.

people[('java', 'backend', 'junior', 'pizza')].append(score)

---

정렬은 한 번만 하기

교재에서도 점수 리스트를 모두 만든 뒤 마지막에 정렬합니다. 이 문제에서 정렬은 이진 탐색을 위한 준비 작업입니다.

쿼리마다 정렬하면 효율이 크게 떨어집니다. 따라서 흐름은 아래처럼 잡아야 합니다.

지원자 정보 저장
각 key의 점수 리스트 정렬
쿼리 처리
bisect_left로 개수 계산

---

핵심 복기

이 문제는 단순히 bisect_left를 아는지만 묻는 문제가 아닙니다.

중요한 흐름은 다음입니다.

1. query마다 info를 모두 보면 시간 초과가 납니다.
2. 조건 검색은 딕셔너리 key로 바꿔야 합니다.
3. '-' 조건은 지원자 저장 시점에 미리 처리합니다.
4. 점수 리스트는 append로 모은 뒤 마지막에 한 번 정렬합니다.
5. 기준 점수 이상 개수는 bisect_left로 구합니다.

이 문제에서 가장 중요한 학습 포인트는 “이진 탐색을 사용할 수 있도록 데이터를 다시 설계하는 것”입니다.