[Lv.1][python] 완주하지 못한 선수

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

프로그래머스

문제는 여기서 확인할 수 있다.

def solution(participant, completion):
    answer = ''
    for i in completion:
        if i in participant:
            participant.remove(i)
            continue
    answer = participant[0]
    return answer

그냥 브루트포스로 for문을 돌렸더니 효율성 테스트에서 모두 실패가 났다...

for문을 돌리고 그 안에서 remove()를 또 사용해 O(n^2)가 된 것이다.

다시 카테고리를 봤더니 해시 문제여서 해시를 사용하기로 했다.

파이썬에서 해시는 딕셔너리로 대체 가능하다.

def solution(participant, completion):
    answer = ''
    part_dict = dict.fromkeys(participant, 0)
    for i in participant:
        part_dict[i] += 1
    for i in completion:
        part_dict[i] -= 1
    for key, val in part_dict.items():
        if val != 0:
            answer = key
    return answer

겉보기에는 for문이 3개나 있어서 더 오래걸릴 것 같아 보이지만, 실제로는 O(n)으로 위의 코드보다 더 빠르게 실행된다.