문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 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명(value=1)이라는 것과 그러므로 참가자가 완주자보다 딱 1명 많다는 것
그래서 다음과 같이 코드를 작성했습니다.
def solution(participant, completion):
for v in completion:
if v in participant:
participant.remove(v)
return participant[0]for문으로 완주자배열을 하나하나 순회하면서 참가자에 속해있으면
해당 선수를 참가자 배열에서 하나하나씩 제거합니다.(remove사용)
그럼 for문 마지막에서는 참가자 배열은 ['미완주자'] 형태로 남게됩니다.
그러므로 인덱스로 첫 번째 인자만 꺼내오면 그 사람이 미완주자인 것 이죠.
하지만 문제가 있었습니다. 정확성은 100프로였는데 속도측정에서 0점을 받았습니다. 시간복잡도가 굉장히 떨어지는 접근법이였다는 얘기입니다.
def solution(participant, completion):
participant.sort()
completion.sort()
for x, y in zip(participant, completion):
if x != y:
return x
return participant[-1]그래서 sort함수를 사용했습니다. sort함수는 오름차순 정렬을 해준 리스트를 다시 뱉어주는 함수죠. for문과 zip을 활용하면 for문 한 번에 두개의 리스트를 순회가능합니다. 그러므로 동시에 순회하면서 같은 인덱스 위치에 없는 요소를 바로 뱉어내고, 아니면 끝까지 가다가 남은 녀석을 뱉어주면 됩니다.
다른 풀이
import collections
def solution(participant, completion):
answer = collections.Counter(participant) - collections.Counter(completion)
return list(answer.keys())[0]컬렉션을 활용하는 방법입니다.
collections의 Counter객체는 생긴건 딕셔너리랑 똑같이 생겼지만 빼기가 가능합니다.(처음 알았네요) 그러므로 남은 key값이 리스트에선 value가 됩니다. 리스트로 바꿔주고 인덱스로 뽑아내면 원하는 결과값이 나오겠네요.
def solution(participant, completion):
answer = ''
temp = 0
dic = {}
for part in participant:
dic[hash(part)] = part
temp += int(hash(part))
for com in completion:
temp -= hash(com)
answer = dic[temp]
return answerhash함수를 활용하는 방법입니다. 같은 문자열이라도 해시값은 달라질 수 있다는 점을 이용한 풀이법입니다. hash() 라는 내장함수의 존재를 또 처음 알았습니다. 코딩을 할 때 bCrypt 라이브러리만 주로 쓰다보니 해쉬나 hashlib에 대해서 지식이 짧았던 것 같습니다. 파이썬에 내장되어있는 hash에 관한 메서드들에 대해서도 공부의 필요성을 좀 더 느꼈습니다.
속도측정에서도 정말 좋은 속도를 보여준 풀이법이였습니다.
