안녕하세요. 탁입니다.

벌써 세번째 포스팅입니다. 글쓰기 쉬운 내용이라 글이 쭉쭉 써져서 너무 좋습니다 ㅎ. 재밌네요.

이번 포스팅부터는 실제 프로그래머스 코딩테스트 고득점 Kit문제를 하나씩 풀어보겠습니다.

첫 문제는 해시 유형의 Level1 문제인 '완주하지 못한 선수' 입니다.

완주하지 못한 선수

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한 사항

  • 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
  • completion의 길이는 participant의 길이보다 1 작습니다.
  • 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
  • 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

입출력 예
3열 × 3행
participantcompletionreturn
["leo", "kiki", "eden"]["eden", "kiki"]"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]["josipa", "filipa", "marina", "nikola"]"vinko"
["mislav", "stanko", "mislav", "ana"]["stanko", "ana", "mislav"]"mislav"

입출력 예 설명

예제 #1

"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2

"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3

"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

나의 풀이

제가 python을 알고리즘 코딩테스트에 사용해야한다고 생각하는 이유 중에 하나입니다.

편리한 기본 함수 모듈이 너무 많습니다.

collections 모듈의 Counter를 사용하면 key-value 형태로 값을 바로 변환할 수 있는데요

이 Counter에는 덧셈/뺄셈을 통해 동일한 key를 가진 값들끼리 value 변화를 줄 수 있습니다.

1. 초기화 상태

Python
3 lines
def solution(participant, completion):
    answer = ''
    return answer

첫 게시글이니깐 상세하게... 노력을 담아서 써보자면..

위와 같이 초기화 상태에서 시작할 때 저는 print() 문을 사용하여 내가 의도하는 방향으로 가고 있는지를 먼저 확인합니다.

2. Counter 선언 확인

Python
8 lines
def solution(participant, completion):
    answer = ''
    print(Counter(participant))
    print(Counter(completion))
    print((Counter(participant)-Counter(completion))
    print(list((Counter(participant)-Counter(completion)).keys()))
    print(list((Counter(participant)-Counter(completion)).keys())[0])
    return answer

이런식으로 정상적으로 내가 의도하는 값을 향해 가고 있는지 확인하는 과정을 거치고요

3. 답안 확인

Python
3 lines
from collections import Counter
def solution(participant, completion):
    return list((Counter(participant)-Counter(completion)).keys())[0]

깔끔하게 답안을 정리합니다.

테스트케이스도 모두 성공했으니 답안을 제출해봅니다.

제출 답안 분석 및 복잡도 확인

Gemini의 도움을 받아 저의 답안에 대한 평가를 해봅니다.

  1. 시간 복잡도: O(N×L)≈O(N)O(N \times L) \approx O(N)
  • 참가자 수를 NN, 완주자 수를 N−1N-1, 문자열(이름)의 최대 길이를 LL (L≤20L \le 20)이라고 할 때:
    • Counter(participant) 생성: NN개의 문자열에 대해 해시값을 계산하고 빈도를 집계하므로 O(N×L)O(N \times L)이 소요됩니다.
    • Counter(completion) 생성: N−1N-1개의 문자열을 집계하므로 O((N−1)×L)O((N - 1) \times L)이 소요됩니다.
    • 카운터 간 뺄셈 (-): 두 해시맵의 키-값 쌍을 비교하며 뺍니다. 최대 NN개의 키를 순회하므로 O(N×L)O(N \times L)이 소요됩니다.
    • keys(), list(), [0] 인덱싱: 차집합 결과 남는 키는 완주하지 못한 단 1개이므로, 리스트 변환 및 인덱스 접근은 O(1)O(1)에 완료됩니다.
  • 종합 결론: 이름의 길이(L≤20L \le 20)는 작은 상수이므로 실질적인 시간 복잡도는 O(N)O(N)입니다. N≤100,000N \le 100,000 조건에서 약 0.03~0.05초 만에 효율성 테스트를 가뿐히 통과합니다.
  1. 공간 복잡도: O(N×L)≈O(N)O(N \times L) \approx O(N)
  • Counter(participant)와 Counter(completion)가 각각 최대 NN, N−1N-1개의 키-값 쌍을 해시 테이블에 저장합니다.
  • 뺄셈 연산의 결과로 생성되는 새로운 Counter 객체(원소 1개)와 list가 생성됩니다.
  • 종합 결론: 입력 배열의 크기에 비례하는 메모리를 사용하므로 공간 복잡도는 O(N)O(N)입니다.
  1. 제출 답안 총평
  • 장점: collections.Counter의 뺄셈 연산자(-)는 중복된 이름(동명이인)까지 개수를 빼서 자동으로 계산해 주므로, 문제의 핵심 예외 조건을 단 1줄로 완벽히 해결하는 매우 파이써닉(Pythonic)한 풀이입니다.
  • 아쉬운 점: 결과로 남은 키가 어차피 1개뿐인데 list(...)로 불필요하게 1칸짜리 배열 객체를 새로 생성한 뒤 [0]으로 꺼내는 사소한 낭비가 있습니다.

AI 추천 답안

아래는 Gemini가 작성해 준 내용입니다.

사용 AI 모델: Gemini 3.8 Flash (Extended)

추천: Counter 최적화형 (실전 숏코딩 & 최우선 추천)

제출 답안의 알고리즘과 장점을 그대로 유지하면서 불필요한 list 변환을 제거한 형태입니다.

Python
5 lines
from collections import Counter

def solution(participant, completion):
    # Counter 뺄셈 후 이터레이터의 첫 번째 요소를 바로 반환
    return next(iter(Counter(participant) - Counter(completion)))
  • 동작 원리: 차집합의 결과인 Counter 객체는 딕셔너리처럼 키 순회가 가능합니다. iter()로 이터레이터를 만들고 next()를 호출하면 리스트를 생성하지 않고 첫 번째(유일한) 키를 O(1)O(1)에 즉시 반환합니다.

제출 답안 vs AI 추천 답안 비교

제출 답안 vs AI 추천 답안 비교
3열 × 3행
비교 항목제출 답안 (Counter-Counter)추천 답안 (next(iter))
시간 복잡도O(N×L)≈O(N)O(N \times L) \approx O(N)O(N×L)≈O(N)O(N \times L) \approx O(N)
공간 복잡도O(N)O(N)O(N)O(N)
추가 메모리1개 원소를 담는 새로운 list 객체 할당 (O(1)O(1))추가 배열 생성 없음 (메모리 O(1)O(1) 즉시 참조)

회고

키 순회가 가능한지도, 해야겠다는 생각까지도 도달하지 못했었는데

아무리 Level1 문항이어도 이렇게 배울 점이 있다는 것이 좋네요.

바로 다음 문제도 또 공부해보겠습니다.

감사합니다.