[프로그래머스] 해시 > 완주하지 못한 선수

1. 생각 정리

• 완주를 못한 사람은 무조건 한 명 존재
• participant 리스트의 길이 = completion 리스트의 길이 +1

 

2. 성공 코드(리스트 sort를 통한 방법)

• 일단 participant, completion 리스트를 정렬한 뒤 쭉 비교
• 비교하다 같은 인덱스에 있는 값이 다르면 return participant [i]

def solution(participant, completion):
    participant.sort()
    completion.sort()
    
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
        
    return participant[-1] #무조건 완주 못한 사람은 한명 있고, participant의 길이가 completion의 길이보다 1 크기 때문

 

3. 성공 코드(해시값을 활용)

• 다른 분들의 풀이를 보다 제가 생각지도 못한 방법이라 정리
• participant 정보를 딕셔너리에 (hash(participant) : participant) 느낌으로 넣어두며 hashval에 모든 해시값의 합을 저장
• completion 리스트를 한 바퀴 돌며 hashval에 모든 completion 요소들에 대한 해시값을 하나씩 빼주면
• 결국 completion에 없는 participant 요소에 대한 해시값만 남게 됨

#completion의 길이는 participant의 길이보다 1 작습니다.
#participant의 모든 해시값의 합 - completion의 모든 해시값의 합 = 완주하지 못한 사람의 해시값
import collections

def solution(participant, completion):
    
    d = dict()
    hashval = 0
    
    for p in participant:
        d[hash(p)] = p
        hashval += hash(p)
        
    for c in completion:
        hashval -= hash(c)
        
    return d[hashval]