[Python] Programmers 코딩테스트 연습 해시 - '완주하지 못한 선수'

Programmers 의 코딩테스트 연습 중, 해시 - '완주하지 못한 선수' 편을 풀어보았다.
https://programmers.co.kr/learn/courses/30/lessons/42576

문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 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"

첫 풀이 (완전히 실패)
처음 문제를 읽고나서 '두 list 를 비교해서 빼면 되겠네' 라고 단순히 생각했는데, 실수였다.
그리고 제일 먼저 드는 생각은 'list 항목을 일일이 for 문 돌면서 비교해야겠다' 였다. 이 역시 실수다. 10만명이라는 인원을 생각하면 N^2 의 계산은 부담이 될 수 밖에 없다는 생각이 들었다.
두 list 를 순회하면서 completion 에 존재하는 것을 participant 에서 제거하는 코드이다. (participant 도 순회를 해야 하기 때문에 복사본에서 삭제해야한다고 생각했다. 잘못됐다.

import copy
def solution(participant, completion):
    answer = []
    par2 = copy.deepcopy(participant)
    comp2 = copy.deepcopy(completion)
    for p in participant :
        for c in completion :
            if p == c : 
                del par2[par2.index(p)]
                del comp2[comp2.index(c)] 
    answer = par2
    return answer

두번째 풀이 (시간 초과)
제한 사항 중,
1. 'completion의 길이는 participant의 길이보다 1 작습니다.'
2. '참가자 중에는 동명이인이 있을 수 있습니다.'
를 유의 깊게 볼 필요가 있다.
1번 제한 사항은 미완주자는 1명이라는 것을 의미한다.
완주자 중 1명씩 돌아가며 완주자명에 일치하는 것을 하나씩 삭제한다. 그럼 한 명만 남을 것이다.
하지만 결과는 성공이나, 효율성 검사(제한시간)에서 실패하였다. for문을 도는것을 없애는 방법을 찾아야했다. list끼리 마이너스 연산이 되면 좋을텐데....

def solution2(participant, completion):
    answer = copy.deepcopy(participant)
    for person in completion:
        del answer[answer.index(person)]
    return answer[0]

세번째 풀이 (성공)
마이너스 연산이 되는것을 찾아 보았다. 집합(set)은 마이너스 연산이 가능하나, 중복이 허용되지 않는다.
검색을 통해 collections 중에 Counter 를 알게되었다.
list 의 원소들을 키로하고 각 원소의 값 중복 카운트를 value로 하여 Counter객체를 반환하는 것이었다. Counter({'mislav': 1})
key들을 반환받고, 리스트로 변환 후 첫번째값을 리턴하였다. (어차피 하나밖에 없을테지만...)

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

학습 후 느낀점

다양한 모듈을 찾아 학습해봐야겠다.
타 언어인 경우, 코드량이 아주 길어지겠지만 python 의 경우 참 편하다는 생각이 들었다.