완주하지 못한 선수
레벨1, 해시
이 문제는 예전에 처음 파이썬 배우고 얼마지나지 않았을 때 풀었던 기억이 있습니다. 오랜만에 풀어보니 이전에 문법도 잘 모르고 어려워했던 기억이 새록새록 나네요 ㅎㅎ
1. 문제 설명
개념 자체는 간단합니다. 마라톤에 참가한 인원(Participant) 중에서 도착한 인원(Completion)을 제외한, 완주하지 못한 인원을 찾아내는 문제입니다.
2. 사고과정 / 나의 풀이
처음엔 당연히 set로 participant - completion 하면 되는거 아닌가? 하고 바로 3초정도 생각하고 바로 질렀지만, 당연하게도 이게 영.. 맞질 않았습니다. 그래서 잠시 문제를 좀 더 자세히 읽어보니 동명이인이 있다고 합니다.
그러면 참가자 명단을 다 만들어두고, 완주자를 하나씩 지워보면 나오겠구나 싶습니다.
그렇게 처음 풀었던 풀이는 아래와 같습니다.
import collections
def solution1(participant, completion):
answer = ''
dic = collections.defaultdict(int)
for p in participant:
dic[p] += 1
for c in completion:
dic[c] -= 1
for i in dic:
if dic[i] != 0:
answer = ''.join(i)
return answer예전에 풀때는 defaultdict라는 함수를 몰라서 하나씩 조건 달아가면서 dict를 만들었던 기억이 있네요. 활용하니까 참 좋습니다.. ㅎㅎ
그런데 이 풀이는 이전에 풀었다보니 다른 풀이를 좀 더 생각해보겠습니다. 완전히 다른 방향으로 해보고싶어서 이번엔 정렬을 해봤습니다.
두번째 방법은, 순서대로 정렬한 후 두개가 달라지는 지점이, 즉 참가자가 완주자에 보이지 않고 넘어간다면, 그 사람이 완주하지 못한 사람이겠구나 하는 생각이었습니다. 해당 코드는 아래와 같습니다.
def solution(participant, completion):
participant = sorted(participant)
completion = sorted(completion)
for i in range(len(completion)):
if participant[i] == completion[i]:
pass
else:
return participant[i]
return participant[-1]
3. 다른 사람의 풀이
아무래도 어렵지 않은 문제이다 보니 다른 사람들의 풀이도 다들 비슷한것같습니다. 다른 방법으로 푸신 코드만 가져오겠습니다.
import collections
def solution(participant, completion):
answer = collections.Counter(participant) - collections.Counter(completion)
return list(answer.keys())[0]개념적으로는 첫번째 풀이와 비슷한것같지만 Counter 객체끼리 빼기가 가능하다는점이 새롭게 다가왔습니다. 조만간 써먹어야겠습니다.
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 answer이분은 정말 문제 유형의 정석대로 해시 함수를 활용하셨더라구요. 역시 개념적으로는 똑같지만 해시를 직접 활용했다는 점이 신기해서 가져와봤습니다.
