[프로그래머스] 완주하지 못한 선수

 

내 풀이

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

 

단순하게 생각을 했고, 테스트가 통과라고 나와서 맞은 줄 알았는데

 

아니었다..ㅎㅎ

효율성에서 문제가 있었다.

참여한 사람의 수가 십만명까지 인정이라 그런 듯하다.

그래서 이럴 때는 해시 함수를 사용하는 것이 시간 복잡도가 O(1)이기 때문에 빠르다고 한다!

 

 

 

다른 사람 답

#1. sort

def solution(participant, completion):
    answer = ''
    participant.sort()
    completion.sort()
    
    for i, j in zip(participant, completion):
        if i!=j:
            return i
    
    
    
    return participant[-1]

 

존재하지 않는 사람을 찾자마자 return 한다라.

동명이인이 있을 경우는 -1 저렇게 하면 되겠구나... 두 리스트를 sort 하면 같은 인덱스에 정렬이 되는 것.

 

#2. hash

def solution(participant, completion):
    answer = ''
    temp = 0
    dic = {}
    for part in participant:
        dic[hash(part)] = part
        temp += int(hash(part))
    for com in completion:
        temp -= hash(com)
    answer = dic[temp]

    return answer

 

hash-map은 key-value 쌍을 관리하는 클래스이다.

문제에서 key는 hash 값이고, value는 선수 이름으로 하였다.

 

각 사용자 문자열 값에 따른 hash값이 존재하게 된다.

 

그렇게 쌓인 hash 값에서 완주한 선수의 hash 값들을 빼주다보면

temp에 남은 해시값은 완주하지 못한 선수의 해시값이 되고

그 해시값을 dictionary의 인덱스에 넣었으므로 꺼낼 수가 있다...

 

값이 같다면, 같은 해시값을 가지게 되는구나 메모.

C에서 주소값은 모두 다른 값일텐데 말이다..

 

#3. Counter

from collections import Counter

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

value로 list에 있었던 원소들은 key값이 되어진다.

dict_result=Counter(participant)-Counter(completion)인데

participant의 딕셔너리에서 completion의 딕셔너리를 빼게되면

결론적으로는 남은 participant의 key가 완주하지 못한 선수가 되어진다.

그리하여 list(dict_result.keys())[0]를 return하면 되어진다.

리스트화 시켜서... [0] 으로 표현. 감탄,,