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

문제 설명

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

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

제한사항

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

입출력 예

participant	completion	return
["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"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

 

 

def solution(participant, completion):
    for i in range(len(participant)):
        if participant[i] not in completion:
            return participant[i]

참가자 중에 동명이인이 있을 수 있다는 조건을 간과하여 위와 같이 코드를 작성하였을 때, 테스트 3 케이스에서 오답이 발생하였습니다.

 

def solution(participant, completion):
    for i in range(len(participant)):
        if participant[i] not in completion:
            return participant[i]
        else:
            completion.remove(participant[i])

코드 실행 중 예상치 못한 시간 초과(Time Limit Exceeded) 문제가 발생했습니다. 문제의 원인을 분석한 결과, remove 메서드의 동작 방식이 문제의 핵심임을 발견했습니다.

remove 메서드의 시간 복잡도

remove는 리스트 전체를 탐색하여 특정 요소를 찾고 제거하는 방식으로 동작합니다. 따라서 시간 복잡도는 O(n) 이 되게됩니다.

그래서 위와 같은 구조에서 for 문과 remove가 결합하게 되어 전체 시간 복잡도가 O(n^2)이 되고, 시간 초과가 나는 것이었습니다.

 

from itertools import zip_longest

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i, j in zip_longest(participant, completion):
        if i!=j:
            return i

시간 초과 문제를 해결하기 위해 itertools 모듈의 zip_longest를 활용했습니다. 이 방법은 두 리스트의 길이가 다를 때 유용하며, 짝이 맞지 않는 부분에는 기본 값을 채웁니다.

문제를 해결하긴 했지만 아래와 같은 점에서 좋은 코드는 아니였다고 생각합니다.. 문제의 출제의도와도 다르고요.

 

• 라이브러리 의존성: itertools 모듈 호출
• 비효율성: 데이터 정렬과 추가 연산

문제를 해결했지만, 장기적으로 더 복잡한 문제를 만나면 이러한 접근 방식이 적합하지 않을 수 있다는 점을 느꼈습니다.

 

zip과 zip_longest는 리스트의 짝을 맞추는 데 사용되지만, 리스트의 길이가 다를 경우 동작 방식이 다릅니다.

zip

• 특징: 짧은 리스트를 기준으로 짝을 맞춥니다.
• 결과: 긴 리스트의 초과 부분은 무시됩니다.

zip_longest

• 특징: 긴 리스트의 길이에 맞춰 None 값을 채웁니다.
• 결과: 모든 요소가 반환되며, 기본 값을 설정할 수 있습니다.