완주하지 못한 선수

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

· 마라톤 경기에 참여한 선수의 수는 100,000명 이하입니다.

· completion의 길이는 participant의 길이보다 1 작습니다.

· 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

· 참가자 중에는 동명이인이 있을 수 있습니다. 

 

입출력 예

participant	completion	return
['leo','kiki','eden']	['eden','kiki']	'leo'
['marina','josipa','nikola','vinko','filipa']	['marina','josipa','nikola','vinko','filipa']	'vinko'
['mislav','stanko','mislav','ana']	['stanko','ana','mislav']	'mislav'

---

풀이

1. Me

def solution(participant, completion):
    participants = {} 
    for i in participant:
        participants[i] = participants.get(i, 0) + 1 
    
    for i, d in participants.items():
        if i in completion:
            participants[i] -= 1 
    
    for i, d in participants.items():
        if d == 1:
            return i 
    return

효율성 테스트 (시간 초과), 정확성 테스트 모두 통과하지 못했다. 시간적인 측면에서 개선을 하기 위해 dictionary 자료형을 이용하여 구현해 보려 하였지만, 실패.. 어느정도 공부를 하고 온 지금, 다시 한번 코드를 짜 보기로 하였다.

 

1) 1차 시도

def solution(participant, completion):
    for i in completion:
        participant.remove(i)
    return participant[0]
    
def solution(participant, completion):
    for i in sorted(participant):
    	if i in sosrted(completion):
            participant.remove(i)
            completion.remove(i)
    return participant[0]

답이 다 맞길래 오잉.. 뭐지 ? 이렇게 간단했나 ? 하고 제출 후 채점 해 보았다.. 그러나 역시는 역시 .. 효율성 테스트 0점이다. 다른 자료구조를 사용해 봐야 할 것 같다.

 

2) 2차 시도

def solution(participant, completion):
    dict_p = {}
    for i in participant:
        dict_p[i] = dict_p.get(i,0) + 1 
    
    for i in completion:
        dict_p[i] -= 1 
    
    return [i for i, d in dict_p.items() if d > 0][0]

dictionary 자료형을 이용해 보았다. get 메서드를 이용하여 참가자 이름을 key 값으로, 참가자 이름이 등장한 수를 value 값으로 가지는 사전을 만들었다. 여기까지는 이전에도 성공했었는데, 문제는 이후부터였다. 완주한 참가자들을 사전에서 한명씩 제거해야 하는데, key, values, items 중 어떤 것을 사용해야 하는지 감이 안 와서 헤맸었다. 하지만 풀이는 생각보다 단순했고, 완주자 배열을 탐색하며 사전의 value 값을 1씩 빼 줌으로써 구현할 수 있었다. 

 

2. Others

import collections

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

collections 라이브러리를 사용했다. 모듈 사용을 능숙하게 하려면 나는 아직 멀었군 .. 

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[len(participant)-1]

내가 dict 자료형을 사용하지 않았으면 구현해야 했을 코드 .. 효율성 테스트 통과를 어떻게 한 거지 .. ?  제거를 하지 않고, 다른 경우에 바로 반환해서 코드 수행 시간이 단축되었나보다.