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

출처: 프로그래머스

풀이과정

처음엔 이중포문으로 participant 배열에서 completion배열의 이름을 찾고
만약 있다면 하나하나 지워가는 방식을 생각해봤는데 그러면 시간복잡도가 n^2이라 코테 등에서 통과되지 못할 것이라 판단해서 시도하지 않았다.

그 다음은 두 배열을 sort해서 비교하는 방법을 생각해봤다.
이건 좀 더 나은 시간복잡도를 가질 것이라고 예상한다.

그렇지만 둘다 해시를 사용하는 것 같지 않아 검색의 도움을 받았다.
해시는 파이썬 dictionary형태로 구현되어있다는 정보에 힌트를 얻어 배열을 {이름: 참가자 수} 형태로 변환하고 두 딕셔너리를 비교하여 참가자 수가 다른 이름을 반환토록 하였다.

def solution(participant, completion):
    hashTable = {}
    
    for name in participant:
        if name in hashTable:
            hashTable[name] += 1
        else :
            hashTable[name] = 1

    for name in completion:
        hashTable[name] -= 1
        
    for key in hashTable:
        if hashTable[key] != 0:
            return key

---

헷갈렸던 파이썬 문법

1. 딕셔너리에 키값이 있는지 판단할 때
   맞는 방법
   if name in table: #아닐 경우 None이 반환됨
   틀린 방법
   if table[name] == None: #KeyError가 발생
2. 증감연산자(++, --)가 없다. 
   직관적인 코드를 위해 사용하지 않는다고 한다. 
   대신 +=, -=를 사용한다.

---

새로 알게 된 모듈

다른사람의 풀이를 확인해보며 위와 같은 과정을 간단히 해주는 collections 모듈이 있다는 것을 알게 되었다.

from collections import Counter

Counter('hello world') # Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

collections.Counter는 직접 for문을 돌리며 셀 필요 없이 한줄로 딕셔너리를 만들어 반환한다.

참고자료: www.daleseo.com/python-collections-counter/

---

시간, 공간 사용