[프로그래머스 Level 1] 완주하지 못한 선수 / 해시 / 파이썬

<문제>

해시(Hash) 구조:

어떤 값을 찾고자 할 때 쓰고 고유한 key와 그 key에 해당하는 값이 저장되는 구조다.

Big-O로는 O(1) 에 해당한다.

파이썬에서는 dictionary로 이를 구현할 수 있다.

 

<풀이>

def solution(participant, completion):
    runners = {}
    for runner in participant:		# 이름(key) - 동명이인 수(value) dictionary
        if runner not in runners:
            runners[runner] = 1
        else:
            runners[runner] += 1

    for runner in completion:		
        runners[runner] += -1
        if runners[runner] == 0:
            del runners[runner]

    ans = list(runners.keys())[0]
    return ans

 

코드 설명:

동명이인이 있을 수 있기 때문에 첫 for문 loop에서는 참가자 정보가 담긴 리스트를 탐색하여 참가자 이름 - 동명이인의 수(없으면 1) 를 key-value pair로 하는 dictionary를 만들었다. 두 번째 for문 loop에서는 완주자 정보가 담긴 리스트를 탐색하는데, 완주자 이름에 해당하는 value를 1씩 빼고 value 가 0이되면 dictionary에서 key-value pair를 지운다. for문을 빠져나오면 runners는 {완주하지 못한 선수 이름:1} 가 된다. return해야할 값은 선수 이름이므로 key값을 가져오게 했다. 

 

+@:

dictionary에서 key값에 value를 mapping(저장)하는 방법 

dict = {}
dict[key] = value

+@:

del 을 이용하면 dictionary의 key - value pair을 지울 수 있다.

dict = {'a':1, 'b':2, 'c':3}
del dict['a']
# 결과: dict = {'b':2, 'c':3}

+@:

return 하기전에 runners.keys() 의 타입이 dict_keys 타입이라서 안의 값을 바로 읽으려하면

TypeError: 'dict_keys' object is not subscriptable 가 뜨게 된다. 따라서 list로 타입을 바꿔준 다음 읽게 했다.

 

##

def solution(participant, completion):
    answer= ''
    P = sorted(participant) # O(nlogn)
    C = sorted(completion) # O(nlogn)
    C.append('..') # 리스트 크기 1 차이나서 index 초과 에러 방지용
    for i in range(len(P)): # O(n)
        if P[i] != C[i]:
            answer = P[i]
            break
    return answer

자료구조를 공부하기 전에는 for문이나 if문 같은 기본적인 문법구조만 알던 때라 sort방법으로 풀었다. 하지만 sort 는 기본적으로 O(nlogn)이기 때문에 리스트 크기가 커질수록 시간효율성이 떨어진다.