[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

def solution(participant, completion):
    answer = 0
    for i in range(len(participant)):
        num = completion.count(participant[i])
        count = participant.count(participant[i])
        if num == count:
            continue
        answer = participant[i]        
        return answer

list.count는 리스트 안에 특정 원소가 있는지 확인하여 개수를 세어주는 함수이다.

정확성은 다 맞았는데 효율성은 다 틀렸다.

정확성, 효율성 테스트가 뭔지 몰라서 찾아봤다.

"[정확성] 테스트는 지원자가 제출한 코드가 문제 지문을 충분히 구현하고 있는지를 평가하며,

[효율성] 테스트는 코드의 시간복잡도(코드가 문제를 해결하는데 걸린 시간이 충분히 빠른지)를 테스트합니다."

내가 작성한 코드는 정답은 맞추나, 시간복잡도가 형편없다는 것이다.. 다시 알고리즘을 구현하자..

성공 # 1

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

내가 처음에 구현한 코드는 리스트의 모든 부분을 검색했기 때문에 시간복잡도가 컸다고 생각했다.

sort 함수를 이용하여 리스트를 알파벳 순으로 정렬하였다.

이 때 무조건 participant는 completion보다 1개 많기 때문에

만약 같은 정렬인데 i번째 원소가 다르다? 그러면 참가자 중 한명은 완수하지 못한 것이 된다.

그리고 for 문을 모두 거칠 때까지 return이 안되면 i번째까지의 참가자는 모두 완수한 것이 되므로

participant[i+1]이 미완수자가 된다.

대다수의 풀이

import collections


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

대부분은 colletions 라이브러리를 이용했다..

colletions 라이브러리의 Counter는 다음과 같이 문자의 개수를 출력해준다.

collections.Counter('hello world')
# Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

따라서 Participant를 리스트 통째로 넣으면 리스트의 원소들의 개수가 몇개인지를 사전형으로 저장한다.

이때 정렬 순서는 개수가 많은 순에서 작은 순이다.

그리고 각 원소의 개수를 참가자와 완수자에 대해 모두 구하고 이를 뺀 값을 answer에 대입한다.

그러면 결국 빼고서 1이 남는 원소는 1개가 될 것이고, 이것이 answer 사전 자료형에 맨 앞에 위치하게 된다.

answer.keys()로 사전 자료형의 key(앞부분)를 추출하고 list로 저장한다.

만든 list의 0번째 인덱스의 원소가 바로 미완수자가 된다.

아직 라이브러리에 익숙하지 못해서 이런 함수가 있는지 처음 알았다.. 외워둬야겠다.

끝으로

프로그래머스에서 처음으로 풀어본 문제인데 바로 틀렸다.

막막하다. 효율성을 제대로 따져서 좀 더 알고리즘을 가볍게 짤 수 있도록 해야겠다.

문제