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

문제

손님별 주문(알파벳 대문자 조합)이 주어진다. course에 적힌 크기마다, 그 크기의 메뉴 조합 가운데 가장 많은 손님이 함께 주문한 조합을 고른다. 2명 이상에게 주문된 조합만 후보가 된다. 최다 조합이 여럿이면 모두 넣는다. 조합 안의 글자와 결과 배열을 모두 사전순으로 정렬해 돌려준다.

  • 손님 2~20명, 주문 하나는 2~10글자
  • course 원소는 2~10

풀이

막히면 한 단계씩 펼친다.

필요한 개념
  • 완전탐색: 주문마다 가능한 조합을 모두 만든다(combinations).
  • 딕셔너리와 집합: 조합마다 몇 명이 주문했는지 센다(Counter).
  • 순열과 조합: 조합은 순서 없는 선택이라 “WX”와 “XW”는 같은 조합이다. 길이 L인 주문에서 크기 k 조합은 C(L, k)개 나온다.
1단계 · 작은 예로 손으로 풀기

주문 [“AB”, “ABC”, “BC”], course [2]

  • 주문마다 두 개짜리 조합: AB → {AB}, ABC → {AB, AC, BC}, BC → {BC}
  • 센다: AB 2명, AC 1명, BC 2명
  • 가장 많은 수는 2이고 2명 이상이다 → AB, BC 둘 다

답은 [“AB”, “BC”]다.

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

방법이 둘 있다.

  • 알파벳 26개로 만들 수 있는 모든 조합을 만들어 몇 명이 주문했는지 센다. 크기 5만 해도 C(26, 5) = 65,780개이고 크기마다 반복하면 많다.
  • 각 주문 안에서만 조합을 만든다. 주문은 최대 10글자라 한 주문의 모든 조합이 2¹⁰ = 1,024개 이하다. 20명이면 2만 개 정도다.

두 번째가 훨씬 적다. 아무도 주문하지 않은 조합은 애초에 셀 필요가 없기 때문이다.

3단계 · 핵심 아이디어
  • 주문 문자열을 먼저 정렬한다. “XWY”와 “WXA”에서 나온 조합이 둘 다 “WX”로 같은 모양이 되어야 한 조합으로 세어진다.
  • 크기 k마다 주문별로 combinations(주문, k)를 만들어 이어 붙인 문자열을 Counter로 센다.
  • 가장 큰 개수가 2 이상이면 그 개수인 조합을 모두 답에 넣는다.
  • 마지막에 답 전체를 사전순으로 정렬한다.
4단계 · 코드 흐름
  1. 주문마다 글자를 정렬해 둔다.
  2. course의 크기 k마다:
    • 모든 주문에서 크기 k 조합을 만들어 센다.
    • 개수의 최댓값이 2 이상이면 그 값인 조합을 답에 넣는다.
  3. 답을 정렬해 돌려준다.
5단계 · 파이썬 코드 
from collections import Counter
from itertools import combinations

def solution(orders, course):
    orders = ["".join(sorted(o)) for o in orders]        # 글자 순서를 맞춘다
    answer = []
    for k in course:
        count = Counter()
        for o in orders:
            count.update("".join(c) for c in combinations(o, k))
        if count:
            top = max(count.values())
            if top >= 2:
                answer += [menu for menu, cnt in count.items() if cnt == top]
    return sorted(answer)
  • sorted(o): 문자열의 글자를 정렬한 리스트다. "".join으로 다시 문자열로 붙인다.
  • combinations(o, k): 글자 k개를 순서 없이 고르는 모든 경우다. 결과는 글자 튜플이라 "".join으로 붙인다.
  • count.update(…): 들어온 값마다 개수를 1씩 늘린다.
  • if count:: 크기 k보다 짧은 주문만 있으면 조합이 하나도 없다. 빈 Counter에 max를 쓰면 오류라 먼저 확인한다.
6단계 · 실행 추적

주문 [“XYZ”, “XWY”, “WXA”], course [2, 3, 4] → 정렬하면 [“XYZ”, “WXY”, “AWX”]

k 센 결과 최댓값 넣는 것
2 XY 2, WX 2, 나머지(XZ, YZ, WY, AW, AX) 1 2 WX, XY
3 XYZ 1, WXY 1, AWX 1 1 없음 (2 미만)
4 없음   없음

답은 [“WX”, “XY”]다. 주문을 정렬하지 않았다면 “XW”와 “WX”가 따로 세어져 WX가 1이 되었을 것이다.

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

주문 N개, 주문 길이 L ≤ 10이면 크기마다 N × C(L, k) 이하, 모든 크기를 합쳐도 N × 2ᴸ 이하다. C(L, 0) + C(L, 1) + … + C(L, L) = 2ᴸ은 글자마다 넣거나 빼는 두 가지라서 나온다. 이항정리에 x = y = 1을 넣은 식이다.

  • 주문을 정렬하지 않아 같은 조합이 다른 문자열로 세어진다.
  • 1명만 주문한 조합을 넣는다. 최댓값이 2 이상일 때만 넣는다.
  • 최다 조합이 여럿일 때 하나만 넣는다.
검증: 문제의 예시 3개를 통과했고, 무작위 주문 2,000묶음에서 “주문에 나온 글자들로 만든 모든 조합마다 그 조합을 품은 주문 수를 집합 포함으로 세는” 느린 풀이와 결과가 같았다 — 16_pg72411_p1.py

  1. 프로그래머스 스쿨, “메뉴 리뉴얼” (https://school.programmers.co.kr/learn/courses/30/lessons/72411), 2026-09-30 조회. ↩