[Programmers Lv.1]완주하지 못한 선수 (Python)

문제

https://programmers.co.kr/learn/courses/30/lessons/42576

내 코드 #1 (실패) 

def solution(participant, completion):
    for i in range(len(completion)):
        if completion[i] in participant: 
            participant.remove(completion[i])
    
    answer = participant[0] if len(participant)  != 0 else ' '
    return answer

내 코드 #2 (성공) 

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for p, c in zip(participant, completion):
        if p != c: 
            return p
    return participant.pop()

다른 사람 풀이 

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

해결 방법

1️⃣ 그냥 간단한 for문으로 완전탐색을 했다. 

     정확성은 다 통과했지만 효율성에서 0점이라니.... 문제 유형인 '해시'를 공부하고 이에 맞게 다시 풀어보았다. 

 

2️⃣ 각 리스트를 정렬하고, 짝을 지어준 다음에 짝이 맞이 않으면 맞지 않는 짝을 return한다.

     다 돌았는데 짝이 모두 맞으면 맨 마지막에 있는 원소가 혼자 다른 원소이기 때문에 pop해준다. 

     이 방법은 participant보다 completion이 항상 1 작기 때문에 가능한 풀이이다. 

 

사실 이 문제의 정답은 마지막 풀이라고 볼 수 있다. 해시 유형에 맞는 풀이 방식으로 풀었기 때문이다. 

해시의 개념은 알지만 파이썬으로 구현하는 방식을 몰라서 공부하고 풀이를 다시 봐야했다. 

파이썬에서의 hash()함수는 key를 생성해준다. 이 풀이에서는 각 participant에 대한 key를 만들고 딕셔너리에 저장했다. 

{-1356185514177201695: 'leo', 5384093445831051978: 'kiki', -8405149115085909459: 'eden'}

이렇게 key가 생성되면, 다 합해서 temp에 합을 저장한다. 

이후에 completion을 돌면서 각 completion의 hash값을 뺀다. (completion과 participant의 값이 동일하면 hash값도 동일) 

마지막에 temp에 남은 수를 key로 딕셔너리에서 값을 찾으면, 그게 정답이 된다.