프로그래머스 완주하지 못한 선수 | set 대신 dictionary를 써야 하는 이유

이 문제는 겉으로 보면 차집합처럼 보이는데,

실제로는 딕셔너리 카운팅 문제다.

처음 보면 참가자 목록에서 완주자 목록 빼면 끝날 것 같아서

set부터 떠올리기 쉬운데,

동명이인 조건 때문에 그 접근은 바로 틀어진다.

핵심은 단순하다.

• 참가자 이름 개수를 세고
• 완주자 이름 개수를 빼고
• 마지막에 값이 남는 이름을 찾으면 된다

즉, 이 문제는 리스트 비교 문제가 아니라

이름 등장 횟수 비교 문제로 보는 게 맞다.

---

🔗 문제 링크

프로그래머스 42576 - 완주하지 못한 선수

https://school.programmers.co.kr/learn/courses/30/lessons/42576

---

문제 정리

문제 조건은 이렇다.

• 참가자 목록 participant
• 완주자 목록 completion
• 완주자는 참가자보다 항상 1명 적다
• 참가자 중 한 명만 완주하지 못했다
• 같은 이름이 여러 번 나올 수도 있다

여기서 바로 봐야 하는 건

동명이인 가능이다.

이 조건 때문에

이 문제는 set으로 풀면 안 된다.

왜냐면 set은 중복을 날려버리기 때문이다.

---

✅ 핵심 아이디어

이 문제는 흐름이 단순하다.

1. 참가자 이름을 딕셔너리에 카운팅한다
2. 완주자 이름을 보면서 카운트를 1씩 뺀다
3. 마지막에 값이 0이 아닌 이름이 정답이다

즉, 이 문제는

누가 있는지가 아니라 누가 몇 번 나왔는지를 보는 문제다.

---

정답

def solution(participant, completion):
    count = {}

    for name in participant:
        if name in count:
            count[name] += 1
        else:
            count[name] = 1

    for name in completion:
        count[name] -= 1

    for name in count:
        if count[name] != 0:
            return name

---

생각해야 하는 부분

이 문제는 해시 문제라고 분류되기도 하는데,

막상 구현할 때 중요한 건

이름을 key로 두고, 등장 횟수를 value로 관리하는 감각이다.

---

1. 왜 set이 아니라 dictionary인가

처음 보면 이런 식으로 풀고 싶어진다.

list(set(participant) - set(completion))

근데 이건 동명이인이 들어오는 순간 깨진다.

예를 들어

participant = ["leo", "kiki", "leo"]
completion = ["leo", "kiki"]

여기서 set으로 바꾸면 둘 다 {"leo", "kiki"}가 돼버린다.

그러면 누가 하나 더 있었는지 정보가 사라진다.

즉, 이 문제는 이름 자체보다 등장 횟수가 중요하다.

그래서 dictionary로 가야 한다.

---

2. 카운팅 구조로 보면 되게 단순해진다

참가자를 먼저 센다.

for name in participant:
    if name in count:
        count[name] += 1
    else:
        count[name] = 1

그다음 완주자를 보면서 뺀다.

for name in completion:
    count[name] -= 1

그러면 마지막에

값이 남아 있는 이름이 완주하지 못한 선수다.

즉, 결국 이 문제는

차집합 문제처럼 보이지만 카운팅 문제다.

---

3. 정렬 풀이도 가능하긴 하다

이 문제는 딕셔너리 말고 정렬로도 풀 수 있다.

def solution(participant, completion):
    participant.sort()
    completion.sort()

    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]

    return participant[-1]

이 방식도 괜찮다.

정렬해두고 앞에서부터 비교하다가

처음 다른 지점이 나오면 그 사람이 완주 못 한 사람이다.

끝까지 같으면 마지막 참가자가 정답이다.

다만 문제를 이해하는 관점에서는

이름 등장 횟수를 직접 다루는 딕셔너리 풀이가 더 본질적이라고 봤다.

---

예외처리 / 주의할 점

⚠️ 1. 동명이인 조건을 절대 빼먹으면 안 된다

이 문제의 핵심은 사실 이 한 줄이다.

“동명이인이 있을 수 있다.”

이 조건 때문에 set 접근이 안 된다.

이걸 놓치면

문제 자체를 잘못 이해한 상태로 가게 된다.

---

⚠️ 2. value가 0이 아닌 이름을 찾아야 한다

참가자는 +1, 완주자는 -1 했으니

정상적으로 완주한 사람은 최종적으로 0이 된다.

즉 마지막에는 이렇게 본다.

for name in count:
    if count[name] != 0:
        return name

여기서 0이 아닌 이름이 바로 정답이다.

---

⚠️ 3. 딕셔너리 key / value 역할을 정확히 나눠야 한다

이 문제에서 딕셔너리 역할은 명확하다.

• key = 이름
• value = 등장 횟수

이걸 헷갈리면

카운팅 구조가 바로 흔들린다.

특히 처음 딕셔너리 문제를 풀 때

key/value 감각이 약하면 여기서 꼬이기 쉽다.

---

내 시행착오

이 문제에서 내가 처음 꼬였던 건 크게 세 가지였다.

---

1. set 차집합으로 먼저 가려고 했다

처음엔 제일 먼저 이 생각이 났다.

answer = list(set(regist).difference(set(goal)))

겉으로는 맞아 보인다.

근데 동명이인 조건 때문에 이 접근은 바로 무너진다.

이 문제는 “누가 있냐”보다

“누가 몇 번 있냐”가 중요하다는 걸 늦게 봤다.

---

2. 딕셔너리를 쓰려고 했는데 값 누적 구조가 안 잡혔다

중간에 딕셔너리로 풀려고도 했는데,

처음엔 이런 식으로 꼬였다.

dict = {}
key = 0

for i in participant:
    dict[i] = key + 1

이렇게 하면

이름마다 값이 누적되는 게 아니라 계속 덮어써진다.

즉, 딕셔너리를 쓴다고 끝나는 게 아니라

누적 카운팅 구조로 봐야 했다.

---

3. 이 문제를 비교 문제로만 봤다

처음엔 참가자랑 완주자 리스트를 비교하는 문제라고만 생각했는데,

실제로는 그보다 카운팅 문제에 더 가까웠다.

이걸 보고 나니까 구조가 훨씬 간단해졌다.

• 참가자 +1
• 완주자 -1
• 남는 사람 찾기

결국 이렇게 정리됐다.

---

한 줄 정리

이 문제는 set 차집합으로 보면 틀리고,이름을 key, 등장 횟수를 value로 두는 dictionary 카운팅 문제로 보면 바로 정리된다.