[코딩테스트, Python] 프로그래머스 '완주하지 못한 선수' 문제 피드백 (Feat. Hash Table)

2022.06.24.

프로그래머스 '완주하지 못한 선수' 문제 피드백 (Feat. Hash Table)

 

 

 

 

 

1번째 시도: 시간 초과

 

def solution(participant, completion):
    
    for i in set(participant):
        if not participant.count(i) == completion.count(i):
            answer = i
            break
    
    return answer

 

최대한 간결하게 코드를 작성하였는데, 시간 초과가 되었다.

 

 

 

 

 

 

2번째 시도: 시간 초과

 

def solution(participant, completion):
    
    check = 0
    
    if not set(participant) == set(completion):
        for i in set(participant):
            if i not in completion:
                answer = i
                break
    else:
        for i in set(participant):
            if not participant.count(i) == completion.count(i):
                answer = i
                break
    
    return answer

 

아까보다는 테스트 5의 실행 시간이 많이 줄었지만,

여전히 시간 초과로, 효율성 테스트는 0점이다. 

 

 

 

 

 

 

---

 

 

 

 

 

모범 답안 (1)

 

import collections

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

 

'collections' module의 'Counter' function에 대해 알게 되었다.

 

• from collections import Counter : 'Counter' function을 쓰려면 'collections' module을 import 해야 함.

Method	Description	Example
Counter( )	string이나 list의 요소를 counting하여 dictionary 형태로 return함.	Counter('aaa bb') => Counter({'a': 3, 'b': 2, ' ': 1}) Counter(['aaa', 'bb']) => Counter({'aaa': 1, 'bb': 1})
Counter( ) .most_common( )	string이나 list의 요소를 counting하여 개수가 많은 순으로 정렬해 tuple array list를 return함.	Counter('aaa bb').most_common( ) => [('a', 3), ('b', 2), (' ', 1)] Counter(['aaa', 'bb']).most_common( ) => [('aaa', 1), ('bb', 1)]

 

 

 

Python의 dictionary는 hash table로 구성되어 있다고 한다.

그래서 대부분의 경우 dictionary가 list보다 훨씬 빠른 시간 복잡도를 가진다고 한다.

앞으로 원소를 찾는 일이 많을 때에는 dictionary를 사용해야겠다.

 

Operation	Dictionary	List
Get Item	O(1)	O(1)
Insert Item	O(1)	O(1) ~ O(N)
Update Item	O(1)	O(1)
Delete Item	O(1)	O(1) ~ O(N)
Search Item	O(1)	O(1)

 

 

 

 

 

 

 

 

모범 답안 (2)

 

def solution(participant, completion):

    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

 

어떻게 이런 생각을 했을까 놀라웠던 코드..

 

participant 안에 있는 Hash 값들을 모두 더한 후,

completion 안에 있는 Hash 값들을 모두 뺀다.

그러면 Hash 값이 하나만 남게 되는데 그게 답이다.

근데 Hash 충돌이 나면 어떻게 해야될까..?

 

 

 

 

 

 

모범 답안 (3)

 

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[-1]

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for p, c in zip(participant, completion):
        if p != c:
            return p
    return participant[-1]

 

 

sort 함수를 먼저 사용한 후 비교하였다.

 

• x.sort( ) : x를 정렬된 상태로 변경함. (ex. x = [3,2,1], x.sort( ), print(x) => [1,2,3])

 

 

 

 

 

 

 

---

 

 

 

 

 

Hash Table

• Hash Table의 소개와 동작 구조

- key와 value가 하나의 쌍을 이루는 data structure.

 

- key를 Hash Function으로 계산하여 그 값을 배열의 index로 사용함. 이때 Hash Function에 의해 반환된 data의 고유 숫자 값을 Hash 값 또는 Hash code 라고 함.

- index 값이 중복되면 collision(충돌)이 일어남 => Linked List 등의 방식을 이용하여 collision 처리

 

- 동작 순서: 원래 데이터의 값(Key) => Hash Function => Hash Function의 결과 = Hash Code => Hash Code를 배열의 Index 로 사용 => 해당하는 Index에 data 넣기

 

 

 

• Hash Table의 장점

- 적은 resource로 많은 data를 효율적으로 관리할 수 있음.

 

- 배열의 index를 사용해서 search, insert, delete가 빠름. (평균 시간복잡도 : O(1))

- key와 Hash 값의 연관성이 없어 보안에도 많이 사용됨.

- data caching에 많이 사용됨.

- get(key), put(key)에 cache logic을 추가하면 자주 hit하는 data를 바로 찾을 수 있음.

 

 

 

• Hash Table의 단점

- 공간 복잡도가 커짐.

 

- Hash Funciton에 대한 의존도가 높아짐.

 

- 순서가 있는 배열에는 어울리지 않음.