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

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

 

해시 언제 사용하면 좋을까?

1. 리스트를 쓸 수 없을 때 

리스트는 숫자 인덱스를 이용하여 원소에 접근하는데 즉 list[1]은 가능하지만 list['a']는 불가능함.

인덱스 값을 숫자가 아닌 다른 값 '문자열, 튜플'을 사용하려고 할 때 딕셔너리를 사용하면 좋음.

 

2. 빠른 접근 / 탐색이 필요할 때 

딕셔너리 함수{} 의 시간복잡도는 대부분 O(1)이므로 아주 빠른 자료구조다.

 

3. 집계가 필요할 때

원소의 개수를 세는 문제는 코딩 테스트에서 많이 출제되는 문제입니다. 이때 해시와, collections 모듈의 Counter 클래스를 사용하면 아주 빠르게 문제를 풀 수 있음.

 

# 원래 코드, 정확도는 맞지만 효율성이 떨어짐

def solution(participant, completion):
    
    for i in completion:
        if i in participant:
            participant.remove(i)
    for j in participant:
        return j
        
# Hash 적용
def solution(participant, completion):
    hash_dict = {}
    sumHash = 0
    for i in participant:
        hash_dict[hash(i)] = i # key: 원래값 해쉬 적용, value: 원래값
        sumHash += hash(i)
    for j in completion:
        sumHash -= hash(j)
    return hash_dict[sumHash]
    
# collections Counter 적용 (list -> dict로 바꿔줌)
from collections import Counter

def solution(participant, completion):
    answer = ''
    dict_result=Counter(participant)-Counter(completion)
    return list(dict_result.keys())[0]