문제 보기 · Level 2 · 2021 KAKAO BLIND RECRUITMENT · 정답률 36% · 푼 사람 11,285명 (2026-09-30 기준)1

문제

지원자마다 "언어 직군 경력 소울푸드 점수"가 주어진다. 문의는 "조건 and 조건 and 조건 and 조건 X" 꼴이고, 조건 자리의 -는 무엇이든 괜찮다는 뜻이다. 문의마다 조건을 만족하면서 점수가 X 이상인 지원자 수를 돌려준다. 정확성과 효율성을 따로 채점한다.

  • 지원자 1~50,000명
  • 문의 1~100,000개
  • 점수 1~100,000

풀이

막히면 한 단계씩 펼친다.

필요한 개념
  • 완전탐색: 지원자 한 명이 맞는 조건 모양(- 포함)을 모두 만든다. 2⁴ = 16가지다.
  • 딕셔너리와 집합: 조건 모양 → 점수 목록.
  • 이분 탐색: 정렬한 점수 목록에서 “X 이상이 몇 명”을 빨리 센다.
  • 곱집합: 16가지 조건 모양은 네 칸의 {값, -}를 차례로 곱한 곱집합이다. product는 이름 그대로 곱집합을 만드는 함수다.
1단계 · 작은 예로 손으로 풀기

지원자 "java backend junior pizza 150" 한 명이 맞는 문의 조건은 네 칸마다 “그 값” 또는 -라서 16가지다.

  • (java, backend, junior, pizza), (java, backend, junior, -), …, (-, -, -, -)

문의 "java and - and - and pizza 100"의 조건 (java, -, -, pizza)는 이 16가지 중 하나다. 그래서 지원자를 미리 16가지 조건 모양마다 넣어 두면, 문의가 오면 그 조건 모양 하나만 꺼내 보면 된다.

2단계 · 가장 단순한 방법과 그 속도

문의마다 지원자 5만 명을 모두 훑어 조건과 점수를 본다. 10만 × 5만 = 50억 번이다. 정확성 테스트는 통과해도 효율성 테스트에서 시간 초과가 난다.

3단계 · 핵심 아이디어

계산을 문의가 오기 전으로 옮긴다.

  1. 미리 모으기: 지원자마다 16가지 조건 모양을 만들어, 딕셔너리 groups[조건 모양]의 목록에 점수를 넣는다. 5만 × 16 = 80만 번이다.
  2. 정렬: 목록마다 점수를 정렬한다.
  3. 문의: 조건 모양으로 목록을 꺼내고, bisect_left(목록, X)로 X 이상이 시작되는 자리를 찾는다. 목록 길이에서 그 자리를 빼면 X 이상인 사람 수다.

떠올리는 신호: “같은 모양의 질문이 아주 많이 온다” → 질문이 오기 전에 답하기 쉬운 모양으로 정리해 둔다.

4단계 · 코드 흐름
  1. 빈 defaultdict(list)를 만든다.
  2. 지원자마다 네 항목과 점수를 나누고, 항목마다 (값, “-“) 두 가지를 조합해 16개 키를 만들어 점수를 넣는다.
  3. 모든 목록을 정렬한다.
  4. 문의마다 “ and “를 빼고 나눠 네 조건과 X를 얻는다. 목록을 꺼내 len - bisect_left를 답에 넣는다.
5단계 · 파이썬 코드 
from bisect import bisect_left
from collections import defaultdict
from itertools import product

def solution(info, query):
    groups = defaultdict(list)                           # 조건 모양 → 점수 목록
    for line in info:
        *fields, score = line.split()                    # 앞 넷은 fields, 마지막은 score
        for key in product(*[(f, "-") for f in fields]): # 16가지 조건 모양
            groups[key].append(int(score))
    for scores in groups.values():
        scores.sort()

    answer = []
    for q in query:
        parts = q.replace(" and ", " ").split()          # ['java', '-', '-', 'pizza', '100']
        key, x = tuple(parts[:4]), int(parts[4])
        scores = groups.get(key, [])
        answer.append(len(scores) - bisect_left(scores, x))
    return answer
  • *fields, score = …: 나눈 조각 중 마지막 하나를 score에, 나머지를 리스트 fields에 담는다.
  • product(*[(f, "-") for f in fields]): 네 칸마다 (값, “-“) 중 하나씩 고르는 모든 조합이다. *는 리스트를 풀어 따로따로 넘긴다.
  • bisect_left(scores, x): x보다 작은 점수의 개수다. 전체에서 빼면 x 이상인 수다.
  • groups.get(key, []): 그 조건 모양의 지원자가 없으면 빈 목록이다.
6단계 · 실행 추적

문의 "- and backend and senior and - 150" → 키 (-, backend, senior, -)

  • 이 키에 들어간 지원자: cpp backend senior pizza 260, python backend senior chicken 50
  • 정렬한 점수 [50, 260], bisect_left([50, 260], 150) = 1
  • 2 − 1 = 1명

예시의 여섯 문의에 대한 답은 [1, 1, 1, 1, 2, 4]다.

7단계 · 복잡도와 흔한 실수

미리 모으기 \(O(16N)\), 정렬 \(O(16N \log N)\), 문의마다 \(O(\log N)\)이다. N = 5만, 문의 10만이면 합쳐서 수백만 번이다.

  • 문의마다 지원자를 훑어 효율성에서 떨어진다.
  • bisect_right를 써서 X와 같은 점수를 빼먹는다. “X 이상”이니 bisect_left다.
  • 문의의 “ and “를 split("and")로 잘라 빈칸이 붙은 조각이 생긴다.
  • 목록을 문의마다 다시 정렬한다. 정렬은 미리 한 번만 한다.
검증: 문제의 예시를 통과했고, 무작위 입력 1,000묶음(지원자·문의 각 최대 30개)에서 문의마다 지원자를 모두 훑는 느린 풀이와 결과가 같았다 — 20_pg72412_p1.py

  1. 프로그래머스 스쿨, “순위 검색” (https://school.programmers.co.kr/learn/courses/30/lessons/72412), 2026-09-30 조회. ↩