[알고리즘] 해시 프로그래머스 1단계 - 완주하지 못한 선수

방법1

def solution(participant, completion):
    
    for p in participant[:]:
        if p in completion:
            participant.remove(p)
            completion.remove(p)
        if len(completion) == 0:
            break
    
    return participant[0]

• remove() 는 처음부터 탐색하는 아주 비효율적인 함수
• O(n^2) 의 시간복잡도

방법2

from collections import Counter

def solution(participant, completion):
    
    no_finished = list(Counter(participant) - Counter(completion))
    return no_finished[0]

새로 배운 내용

from collections import Counter

from collections import Counter

x = ['a', 'b', 'c']
y = ['a', 'b']

print(Counter(x))
print(Counter(y))
print(Counter(x).keys())
print(Counter(x).values())
print(Counter(x).items())

<output>
Counter({'a': 1, 'b': 1, 'c': 1})
Counter({'a': 1, 'b': 1})
dict_keys(['a', 'b', 'c'])
dict_values([1, 1, 1])
dict_items([('a', 1), ('b', 1), ('c', 1)])

Counter 빼는 2가지 방법

Counter(x) - Counter(y)

Counter({'c': 1})

Counter(x).subtract(Counter(y))

Counter({'a': 0, 'b': 0, 'c': 1})