[programmers] 해시 - 완주하지 못한 선수

문제

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

---

My Solution

Idea 1. remove 사용

def solution(participant, completion):
    for person in completion:
        participant.remove(person)
    
    return participant[0]

• list의 remove()는 시간 복잡도가 O(1) ~ O(N) ⇒ 효율성 테스트 통과 불가

Idea 2. dict, counter 사용

from collections import Counter

def solution(participant, completion):
    dict_participant = dict(Counter(participant))
    
    for key in completion:
        if dict_participant[key] != 1: # 동명이인이 있는 경우
            dict_participant[key] -= 1
        else:
            dict_participant.pop(key)
    
    return list(dict_participant.keys())[0] # key 추출

• 빠른 접근과 삭제가 가능한 해시(dict) 자료구조를 사용한다.

---

Other’s Solution

• https://school.programmers.co.kr/learn/courses/30/lessons/42576/solution_groups?language=python3

Idea. Counter() 사용

import collections

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

• Counter 객체 간의 뺄셈을 이용한 방법
• Counter에 관련 글