완주하지 못한 선수

📖 해시 > 완주하지 못한 선수

• 한 명 제외하고는 모든 선수가 완주 → 완주하지 못한 선수 이름 출력
• 동명이인이 있을 수 있음

📖What I thought

• 동명이인이 있으므로 set을 활용할 수는 없음
• participant, completion 두 리스트를 비교해야 해
  1. 비교 시 2중 for문을 사용한다면 O(n^2) 너무 느려 → 효율성 통과 못할 듯 (참여선수 10만명 이하 → 시간복잡도 100억 ㄷㄷ)
  2. 우선 participant, completion 두 리스트를 정렬한 후 같은 index에 해당하는 값끼리 비교해보자궁 O(nlogn)

📖풀이

📎Sort & Loop

def solution(participant, completion):
    participant.sort()
    completion.sort()
 
    for p, c in zip(participant, completion):
        if p != c:
            return p
 
    return participant[-1] # zip으로 끝까지 돌았는데 여기까지 왔으면 마지막 사람이 정답

• 정렬 후 순서대로 리스트를 비교했을 시 같은 인덱스에 다른 값이 있으면 그 때의 participant 값이 정답
• 🚨 zip()으로 묶으면 더 작은 개수를 가진 iterable의 수만큼 zip됨 → 끝까지 for문을 돌아도 정답을 못찾을 수 있음 → 가장 마지막 사람이 정답
• 시간 복잡도 O(nlogn)

📎Dictionary

def solution(participant, completion):
    h = dict()
    
    for p in participant:
        h[p] = h.get(p, 0) + 1
 
    for c in completion:
        if h[c] > 1:
            h[c] -= 1
        else:
            del h[c]
 
    return ''.join(h.keys())

• 해시 문제니까 ㅎㅎ;; 해시를 사용해보자 → 그렇다면 이름이 주어지면 몇 번이나 등장했는지를 담는 해시 테이블을 만들어보자 → 이름을 key 값으로 두고 등장횟수를 value로 두자
• ⭐️실제 시험에선 문제 분류를 해주지 않으니까 탐색 과정이 많음 → hash(dictionary) 활용 기억해두자
• 가장 빠룸 O(n)

📎Counter

from collections import Counter
 
def solution(participant, completion):    
    cf = Counter(participant) - Counter(completion)
    
    player = list(cf.keys())[0]
    
    return player

• Counter는 리스트 원소와 해당 원소의 개수를 Counter 객체로 return 해줌
• 심지어 비교 연산도 가능하다
• 비교해서 차이남는 하나 고것이 정답이올시다

📖What I learned

1. zip() 사용 시 두 iterable의 수가 맞지 않는다면 앞에서부터 순서대로 더 작은 개수를 가진 iterable의 수만큼 zip 된다는 것
2. 탐색이 많이 필요한 문제에 해시 테이블을 사용하자
3. Counter 객체끼리는 빼기 연산이 가능 (심지어 dictionary처럼 key, value 각각 접근도 가능)

📖관련 지식

📎Hash Table

📎Counter

📎zip