문제 보기 · Level 1 · 고득점 Kit · 해시 · 정답률 60% · 푼 사람 119,670명 (2026-09-30 기준)1

문제

마라톤 참가자 명단과 완주자 명단이 주어진다. 완주하지 못한 사람은 정확히 한 명이다. 그 사람의 이름을 돌려준다.

  • 참가자 1~100,000명
  • 완주자 명단은 참가자보다 1명 적다
  • 동명이인이 있을 수 있다

풀이

막히면 한 단계씩 펼친다.

필요한 개념

딕셔너리와 집합: 이름별로 몇 명인지 세는 표. Counter를 쓰면 더 짧다.

1단계 · 작은 예로 손으로 풀기

참가자 [“kim”, “lee”, “kim”], 완주자 [“lee”, “kim”]

  1. 참가자를 이름별로 센다: kim 2명, lee 1명
  2. 완주자만큼 뺀다: kim 2 − 1 = 1, lee 1 − 1 = 0
  3. 1명이 남은 이름 → “kim”

“kim”이 두 명이라 “명단에 있나 없나”만 보면 안 된다. 몇 명인지 세야 한다.

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

참가자마다 완주자 명단에서 찾아 지운다. 찾기와 지우기가 리스트에서는 명단을 훑는 일이라, 10만 × 10만 = 100억 번이다. 시간 안에 끝나지 않는다. 자세한 셈은 시간 복잡도로 방법 고르기의 예시에 있다.

3단계 · 핵심 아이디어

이름을 키로, 인원을 값으로 하는 딕셔너리를 만든다. 딕셔너리는 이름으로 칸을 바로 찾으니 한 사람을 처리하는 데 평균 한 번이면 된다.

  1. 참가자를 돌며 이름별 인원을 1씩 늘린다.
  2. 완주자를 돌며 1씩 줄인다.
  3. 0보다 큰 이름이 답이다.

떠올리는 신호: “두 명단을 비교”, “동명이인” → 이름별 개수를 센다.

4단계 · 코드 흐름
  1. 빈 딕셔너리 count를 만든다.
  2. 참가자 이름마다 count[이름] += 1 (처음이면 0에서 시작).
  3. 완주자 이름마다 count[이름] -= 1.
  4. count를 돌며 값이 0보다 큰 이름을 돌려준다.
5단계 · 파이썬 코드 
def solution(participant, completion):
    count = {}
    for name in participant:
        count[name] = count.get(name, 0) + 1   # 없으면 0에서 시작
    for name in completion:
        count[name] -= 1                       # 완주자는 반드시 참가자이므로 키가 있다
    for name, c in count.items():              # (이름, 인원) 쌍을 차례로 꺼낸다
        if c > 0:
            return name
  • count.get(name, 0): name이 표에 없으면 0을 돌려준다.
  • count.items(): 딕셔너리의 (키, 값) 쌍을 차례로 꺼낸다.

Counter를 쓰면 세기와 빼기가 한 줄이다.

from collections import Counter

def solution(participant, completion):
    left = Counter(participant) - Counter(completion)   # 빼고 0 이하인 이름은 사라진다
    return list(left)[0]                                # 남은 이름은 하나뿐
6단계 · 실행 추적

참가자 [“kim”, “lee”, “kim”], 완주자 [“lee”, “kim”]

단계 한 일 count
참가자 kim 0 + 1 {kim: 1}
참가자 lee 0 + 1 {kim: 1, lee: 1}
참가자 kim 1 + 1 {kim: 2, lee: 1}
완주자 lee 1 − 1 {kim: 2, lee: 0}
완주자 kim 2 − 1 {kim: 1, lee: 0}

값이 0보다 큰 kim을 돌려준다.

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

명단을 두 번 훑으니 평균 \(O(n)\)이다.

  • set(participant) - set(completion)처럼 집합의 차를 쓰면 동명이인에서 틀린다. 집합은 같은 이름을 하나로 합쳐서, 위 예에서는 빈 집합이 된다.
  • 두 명단을 정렬해 앞에서부터 나란히 비교하는 방법도 맞다. 처음으로 달라지는 자리의 참가자가 답이고, 끝까지 같으면 참가자 명단의 마지막 사람이 답이다. 비용은 정렬 때문에 \(O(n \log n)\)이다.
검증: 문제의 예시 3개를 통과했고, 동명이인을 많이 섞은 무작위 입력 2,000개에서 딕셔너리 풀이, Counter 풀이, 정렬 풀이가 모두 같은 답을 냈다 — 04_pg42576_p1.py

  1. 프로그래머스 스쿨, “완주하지 못한 선수” (https://school.programmers.co.kr/learn/courses/30/lessons/42576), 2026-09-30 조회. ↩