[프로그래머스] 완주하지 못한 선수 with python (feat. hash)

해시 테이블

Key & Values

- 해시 테이블은 value와 key를 가짐

- 딕셔너리와 다른 점은 key가 계산된 숫자 시퀀스 혹은 char

- 배열을 사용해서 연속적이지 않은 buckets라고 불리는 구조에 저장

- 각 값의 위치는 해시 함수에 의해 계산

 

해시 충돌(collisions)

다른 값을 input 했지만 같은 hash값을 가지는 경우(다른 값이라도 같은 해시를 가질 수 있지만 같은 해시 값이라 해서 같은 인스턴스는 아님 -> 단방향)

 

해시의 장점

중복을 허용하지 않기 때문에 중복되지 않는 데이터 값을 가져야 하는 구조에서 사용할 수 있다.

특히 그 크기가 어떻든 간에 값을 찾는 시간 복잡도가 O(1)이기 때문에 크기가 큰 데이터에서 값을 효과적으로 찾을 수 있다.

 

딕셔너리를 사용한 이유

딕셔너리는 키에 값이 들어 있는 경우 값을 반환하지만 get()을 사용하는 경우 key에 값이 없을 때 false를 반환함.

이를 사용하여 배열을 정렬하지 않고 원하는 값을 찾아내기 위해 사용함

그러나 중복된 이름을 가지는 사람이 있어 리스트 자체를 비교하는 것도 좋은 방법이었다.

 

새롭게 알게 된 것

import collections

collections.Counter(이터레이터형 객체) -> 서로 연산 가능

 

hash() -> 해시 값 반환

 

제출용 코드

def solution(participant, completion):
    
    a = dict()
    
    for i in completion :
        if a.get(i):
            a[i] += 1
        else:
            a[i] = 1
    for i in participant :
        if not a.get(i) :
            return i
        else: 
            a[i] -= 1
            
            if a.get(i) < 0:
                return i

추가 : Swift 

해쉬 사용하지 않고 정렬로 간단하게 풀 경우 비교 해주어도 된다.

이렇게 하면 중복되는 이름을 가진 선수를 복잡하게 구하지 않아도 된다. 

다만 sort 때문에 입력 값에 따라 시간 복잡도가 증가할 수 있다.

class Solution {
    func programmersProblem(_ participant: [String], _ completion: [String] -> String) {
        var par = participant
        var com = completion

        par.sort()
        com.sort()
        
        for i in 0..<com.count {
            if par[i] != com[i] {
                return par[i]
            }
        }
        
        return par[par.count-1]
        
    }
}