[프로그래머스] 해시 파이썬

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

프로그래머스

 

 

내 코드

from collections import defaultdict

def solution(participant, completion):
    hash_table = defaultdict(int)
    for i in participant:
        hash_table[i] += 1
        
    for i in completion:
        hash_table[i] -= 1
        if hash_table[i] == 0:
            del hash_table[i]
    return list(hash_table.keys())[0]

해당 코드는 O(N)의 시간 복잡도를 가집니다.

---

Review

처음에 문제를 풀 때는 O(N²)의 시간 복잡도로 문제를 풀었습니다.

처음에 작성한 코드는 아래와 같습니다.

# 효율성 케이스에서 탈락한 코드
def solution(participant, completion):
    for i in participant:
        if i not in completion:
            return i
        else:
            completion.remove(i)

 

N² 의 시간 복잡도가 걸리는 이유:

for 문 : O(N)

remove() 함수 시간 복잡도 : worstcase 일 경우 O(N)

그래서 이렇게 뜨면 매우 정상이에요

---

따라서 문제에 의도대로 O(N²) 보다 낮게 문제를 풀어야겠다고 생각했습니다.

저는 딕셔너리를 사용했습니다.
defaultdict 은 초기 키값이 없을 때 유용하게 사용할 수 있는데요

defaultdict에 대한 설명은 아래 링크 참고 부탁드립니다!
https://thingjin.tistory.com/entry/Python-defaultdict-%EB%94%95%EC%85%94%EB%84%88%EB%A6%AC-%EA%B8%B0%EB%B3%B8%EA%B0%92-%EC%84%A4%EC%A0%95%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95

[Python] defaultdict 딕셔너리 기본값 설정하는 방법

---

입출력 예 3번을 예시로 보겠습니다.

입출력 3번

for i in participant:
    hash_table[i] += 1

# defaultdict(<class 'int'>, {'mislav': 2, 'stanko': 1, 'ana': 1})

1. 해당 코드를 적용하면 주석과 같은 결과 값이 나옵니다.

 

for i in completion:
    hash_table[i] -= 1
    if hash_table[i] == 0:
        del hash_table[i]

2. completion을 순회하면서 완주를 한 사람이면 1씩 빼주고
이후 0이면 그 해시테이블에서 빼주는 식으로 코드를 짰습니다.

 

return list(hash_table.keys())[0]

3. 마지막으로 딕셔너리키값의 하나남은 원소를 return 해주면 됩니다.

 

 

참고로 딕셔너리의 del은 선형시간 = O(1)으로 값을 제거 할 수 있습니다.

del hash_table[i]

딕셔너리 같은 경우 리스트(배열) 과 달리 선형시간O(N)으로 값 제거 

 

 

다른 풀이 방법이 있다면 댓글로 공유 부탁드립니다.
( ̳• ·̫ • ̳)

질문이나 지적할 사항 있으면 언제든지 의견 주세요
（ •́ .̫ •̀ ）