[프로그래머스]완주하지 못한 선수

[20] 완주하지 못한 선수

책 구매하기

문제 정보

• 분류: 해시
• 정답률: 54%
• 권장 시간 복잡도: O(N)
• 핵심 키워드: 해시, 카운팅, 동명이인, 완주자 차감
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42576

문제를 읽을 때 체크할 포인트

set으로 끝낼 수 있을 것 같지만 동명이인이 있다는 순간 카운팅 문제로 바뀐다. 참가자 수를 세고 완주자를 빼서 마지막에 1이 남는 이름을 찾으면 된다.

배열을 처음부터 끝까지 비교하는 쪽으로 가면 코드는 길어지고 예외도 많아진다. 이 문제는 필요한 정보를 키-값으로 압축하는 순간 풀이가 짧아진다.

풀이 흐름

1. 참가자 이름별 등장 횟수를 딕셔너리에 센다.
2. 완주자 배열을 돌며 해당 이름의 횟수를 1씩 줄인다.
3. 최종적으로 값이 1 이상 남은 키를 반환한다.

구현할 때 놓치기 쉬운 부분

이 문제에서 가장 많이 틀리는 지점은 동명이인 처리다. 참가자 이름을 집합으로만 관리하면 같은 이름이 여러 번 등장하는 경우를 처리할 수 없다. 이름별 개수를 세고, 완주자 이름이 나올 때마다 하나씩 차감하는 흐름으로 가져가야 한다.

파이썬 정답 코드

from collections import Counter

def solution(participant, completion):
  # 참가자 이름별 등장 횟수를 딕셔너리에 센다.
  counts = Counter(participant)
  # 완주자 배열을 돌며 해당 이름의 횟수를 1씩 줄인다.
  for name in completion:
    counts[name] -= 1
  # 최종적으로 값이 1 이상 남은 키를 반환한다.
  for name, count in counts.items():
    if count:
      return name

시간 복잡도

N은 participant의 길이이고, completion의 길이는 N-1이다.

입력을 앞에서 뒤까지 한 번 순회하면서 비교하거나 카운트를 갱신하는 구조이다. 원소 하나를 처리할 때 붙는 비용은 상수 시간이라 전체 비용은 N번 처리 비용으로 끝난다.

따라서 시간 복잡도는 O(N)이다.