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

- 문제 설명

 

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

마라톤에 참여한 선수들의 이름이 담긴 배열 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는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

 Level 1 답게 문제는 아주 명확합니다. 마라톤 참가자(Participant) 중에 완주한 선수(completion) 을 제외한 사람의 이름을 Return 하면 됩니다. 이 때 완주하지 못한 사람은 "1명"입니다.

 문제를 이해하셨다면 입출력 예시에서 주목해야할 점은 "예제 #3" 입니다. 동명이인이 있을 수 있다는 것은 배열에서 중복을 허용한다는 것입니다. 중복을 허용하지 않는다면 Python 의 Set자료형을 이용하여 difference를 이용한다면 바로 풀리겠지만...

 

def solution(participant, completion):
	participant_set = set(participant)
    	completion_set = set(completion)
    	result =participant_set.difference(completion_set)
    	result =list(result)
    	return reslut[0]

위와같이 코드를 작성했을 경우 예제 #3은 결과가 빈 리스트가 반환되므로 Out of Index 에러가 발생하여 코드가 돌아가지 않습니다. 

 

for i in completion:
        if i in participant:
            participant.remove(i)

다음으로 정말 간단하게 완전탐색 기법으로 완주한 선수들(Completion) 에 있는 항목들을 차례로 참가자들(Participant)에 비교하여 있으면 participant 리스트에서 제거하는 식으로 해보았더니 정답은 맞추지만, 효율성 검사에서 모두 실패가 됐습니다. 

Participant 가 N개라면 Completion은 N-1개이므로 완전 탐색을 위해서는 Time Complexity 가 O(N^2) 이 되므로 매우 비효율적입니다. 따라서 코드를 다음과 같이 수정해보았습니다.

 

import collections as col

def solution(participant, completion):
    return list((col.Counter(participant) - col.Counter(completion)).keys())[0]

collections 모듈의 Counter 객체를 사용해서 중복을 허용하는 딕셔너리 형태의 객체를 만들어 서로 차집합을 해주는 것입니다. 논리 연산을 수행하므로 Time Complexity도 완전 탐색에 비해 많이 낮아지는 효율적인 코드를 구현할 수 있습니다. 딕셔너리형 자료형을 이용하여 set형태로 만들어 difference 를 사용하는 새로운 코드를 짜볼 수 있겠지만 파이썬스러운 코드를 추구하기 때문에 collection이라는 모듈을 사용하여 간결하게 작성해보았습니다.