[Python] 완주하지 못한 선수

문제 설명 및 링크

완주하지 못한 선수 링크

접근 방법 및 해결 전략

1. for 문을 통해 participant의 요소들을 completion과 비교해서 정답을 출력하려고 했지만 시간 효율성 검사를 통과하지 못했다.
2. 파이썬의 dictionary를 활용해서 조회 시간을 O(1) 상수 시간에 가깝게 하려고 노력했다.
3. 경우의 수는 2가지 동명이인 중에 완주하지 못한자, 동명이인이 아닌 사람 중 완주하지 못한자이다. 동명이인이 아닌 사람은 찾기 쉬웠지만 동명이인이 여러명이라면 찾기 어려웠다. 예를 들어, participant : [sam,sam,sam,john,john] completion : [sam,sam,sam,john]이라면 동명이인이 가장 많다고 정답일 수 없고 적다고 해도 정답이라고 확신할 수 없다. 검색을 통해 hash()함수에 대해 할게 되어 이를 활용했다.
   hash()함수는
   1. 동일한 입력값에 대해서 항상 동일한 해시값(정수)을 반환한다.
   2. 많은 양의 데이터를 빠르게 계산할 수 있다.
   3. 입력값에 상관없이 항상 같은 크기의 해시값을 반환한다.

코드 작성 및 설명

첫 번째

def solution(participant, completion):
    result = []
    for c in participant:
        if c not in completion:
            return c
        elif c in completion and c not in result:
            result.append(c)
        else:
            return c

단순하게 for문으로 비교해서 completion에 없는 participant를 찾고자 했지만 효율성 테스트는 하나도 통과하지 못했고 정확성 테스트도 테스트5, 6을 통과하지 못했다.
동명이인인 이름이 2가지가 이상 일때, 위의 sam과 john 같은 테스트 케이스를 걸러내지 못한다.

두 번째

def solution(participant, completion):
    hash_table = {}
    
    for c in completion:
        hash_table[c] = 0
        
    for p in participant:
        if p in hash_table: 
            hash_table[p] += 1
        elif p not in hash_table:
            return p
        
    for key, value in hash_table.items():
        if value == 2:
            return key

두 번째 코드는 정확성 테스트 5와 효율성 테스트 5를 통과하지 못했다. 마찬가지로 동명이인인 이름이 2가지가 이상 일때, 위의 sam과 john 같은 테스트 케이스를 걸러내지 못한다.

마지막

def solution(participant, completion):
    hash_table = {}
    sum_hash = 0
    for p in participant:
        hash_table[hash(p)] = p
        sum_hash += hash(p)
        
    for c in completion:
        sum_hash -= hash(c)  
    
    return hash_table[sum_hash]

검색을 통해 hash()에 대해 알게 되었다. dictionary로 hash_table을 만들어 조회 시간을 줄이고 sum_hash를 활용해 유일한 입력값을 찾고자 했다. completion의 요소들을 hash로 변환해 sum_hash에서 모두 빼면 남은 hash값이 participant에 남아있는 요소이게 된다.