[프로그래머스] 완주하지 못한 선수(해시Lv1) - 파이썬

문제 설명

  수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

입출력 예 설명

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

1. 루프를 이용한 방법

처음에 그냥 떠오르는대로 작성한 코드이다. 해시문제이지만 해시를 사용하지 않고 풀었다.

def solution(participant, completion):
     
    for i in participant:
        if i not in completion:
            answer = "".join(i)
            break
        else:
            completion.remove(i)
            
    return answer

정확성 테스트는 다 통과하지만 효율성 테스트에서는 시간 초과가 떴다.
아마 첫 번째 제한사항인 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. 에서 테스트케이스의 리스트 크기가 몇 만으로 주어진 것 같다.
루프문에서 리스트의 인덱스를 전부 돌려고 하니 그만큼 시간이 많이 소비된듯 하다.

2. 해시를 이용한 방법

그래서 효율성 테스트를 통과하도록(본래 문제 의도에 맞게) 해시를 사용해서 문제를 풀어야한다.
딕셔너리 자료형과 hash() 파이썬 내장함수를 사용하여 작성하였다.

해시란?

  해시(hash)란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값이다. 이를 이용해 특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. 기존에 사용했던 자료 구조들은 탐색이나 삽입에 선형시간이 걸리기도 했던것에 비해, 해시를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더욱 빠른 속도로 처리할 수 있다.
해시넷

def solution(participant, completion):
    part_dict={}
    hashSum = 0
    
    for part in participant:
        part_dict[hash(part)] = part
        hashSum += hash(part)
    
    for comp in completion:
        hashSum -= hash(comp)
    
    answer = part_dict[hashSum]
            
    return answer

• 첫 번째 루프에서 participant의 마라토너들의 이름을 hash()함수로 해시값으로 변환하여
  해시값을 Key, 이름을 Value로 하여 딕셔너리에 대입해준다.
  그리고 hashSum에 Key값을 계속해서 더해준다.
• 두 번째 루프에서 completion에 있는 마라토너들의 이름들 또한 해시값으로 변환하여 차례대로 hashSum에서 빼주면 결국 완주하지 못한 마라토너의 이름을 해시한 해시값(key값)만 남게 된다.
• 결국 이 key값을 이용하여 딕셔너리에서 key값에 대응하는 value값을 찾으면 답이 된다.

추가) 파이썬 hash() 함수

파이썬에서 기본으로 제공하는 hash()함수에 대해서 찾아봤으나 해시에 대한 설명만 나오는 글이 많고 hash()함수 자체에 대해 정리해 놓은 곳을 찾을 수 없었다.
그래서 간단히 hash()함수의 출력값이 어떻게 나오는지만 확인해보겠다.

다음과 같이 정수형을 함수에 전달인자로 준 것과 문자를 전달인자로 준 것을 출력해봤다.

hash_num = hash(1)
hash_string = hash("a")

print(hash_num)
print(hash_string)

다음과 같이 정수형은 그대로 출력되고 문자열 자료형은 해시되어 해시값이 출력되는 것을 확인 할 수 있다.

그리고 더 실행해보면 아래와 같이 실행할 때마다 해시값이 달라 지는 것을 알 수 있다.

다음과 같은 코드를 실행해보면

hash_string1 = hash("a")
hash_string2 = hash("a")
hash_string3 = hash("ab")
hash_string4 = hash("ab")

print(hash_string1)
print(hash_string2)
print(hash_string3)
print(hash_string4)

당연하겠지만 같은 문자열에 대해서는 같은 해시값이 출력되며 문자열이 더 길다고 더 큰값이 출력되는 것도 아니라는 것을 알 수 있다. 즉 랜덤하다.

그리고 파이썬에는 따로 hashlib라는 해시라이브러리가 존재한다.
hashlib를 import해주면 sha함수를 쓸 수 있다.