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

1. 문제

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

---

2. My Solution

2.1. Idea 1. remove 사용

      

      

      

    
    

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

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

2.2. Idea 2. dict, counter 사용

      

      

      

    
    

      <python />
    
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) 자료구조를 사용한다.

---

3. Other’s Solution

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

3.1. Idea. Counter() 사용

      

      

      

    
    

      <python />
    
import collections

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

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