[Python] 프로그래머스 Lv1. 완주하지 못한 선수

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

프로그래머스

문제

• 참가자 이름을 포함하는 리스트와 완주자 이름을 담은 리스트가 주어짐.
• 참가자 중 완주하지 못한 사람을 리턴하는 문제
• 동명이인이 있을 수 있으며, 참가자 리스트는 완주자 리스트보다 크기가 1만큼 크다.

---

우선 참가자수가 최대 100,000명 이기 때문에 효율 측면에서 어떻게 코드를 작성할 지가 중요하다고 생각했다.

딕셔너리를 이용해보면 어떨까 생각했고 두 개의 반복문을 이용해 코드를 만들어보았다.  

첫번째 방법 

: 참가자 이름을 key로 가지는 딕셔너리를 생성하고 value는 이름이 나온 횟수로 설정. 완주자 리스트를 순회하며 나오는 이름의 value를 1씩 감소시키고, 0이 되면 pop하여 삭제한다. 

정확성 테스트는 모두 통과했지만  효율성 테스트에서 모두 실패했다. 다른 방법이 필요하다.

def solution(participant, completion):
    dic={}
    for name in participant:
        if name in list(dic.keys()):
            dic[name] += 1
        else:
            dic[name] = 1
    for goal in completion:
        dic[goal] -= 1
        if dic[goal] == 0:
            del dic[goal]
    return list(dic.keys())[0]

두번째 방법

: 참가자와 완주자 리스트 각각을 정렬한 후 다른 부분 찾기 

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(0,len(completion)):
        if(participant[i] != completion[i]):
            return participant[i] #i번째 원소가 다른 경우

    return participant[len(participant)-1] #마지막 참가자가 완주하지 못한 경우

위 방법으로는 테스트를 통과하였다. 하지만 이 문제에 떡하니 '해시문제' 라고 써있는 걸 본 이상 그냥 넘어갈 수가 없었다. 

마치 로피탈의 정리를 이용해 문제를 푼 느낌...

그래서 해시함수를 공부해보았다.

a = 'coding'
hash(a)

위와 같이 hash() 함수는 입력된 데이터를 임의의 정수로 변환해준다. 이를 활용해 코드를 작성할 수 있다.

def solution(participant, completion):
    dic={}
    hash_sum=0
    for name in participant:
        dic[hash(name)] = name
        hash_sum += hash(name)
    
    for goal in completion:
        hash_sum -= hash(goal)
    
    return dic[hash_sum]

원리는 아주 간단한데, 참가자의 이름을 hash() 함수에 통과시킨 값을 key, 이름을 value로 하여 딕셔너리에 저장한다. 

hash 값의 합을 저장하는 변수(hash_sum)를 선언한다. 그리고 완주자 리스트를 순회하며 각각의 hash()값을 구하고, 이를 hash_sum에서 빼준다. 순회가 끝났을 때 남은 hash_sum값이 완주하지 못한 사람의 hash 값이 되는 것이다. 

---

해시를 활용한 문제는 매우 중요하다고 한다. 첫번째 코드에서 딕셔너리의 key값을 탐색할 때 시간이 오래걸렸지만 hash()함수를 이용한 결과 효율성 테스트도 통과할 수 있었다.