[파이썬] 프로그래머 알고리즘 고득점 Kit - 해시 / 완주하지 못한 선수 완벽해설

문제

 

 

해설

 

이 문제의 경우 아무렇게 풀면 효율성 문제로 풀리지 않는다.

 

def solution(participant, completion):
    answer = ''
    for comp in completion:
        participant.remove(comp)
    answer = participant[0]
    return answer

 

예를 들어 위처럼 리스트를 만들고 pop하는 방식으로 하게 되면 리스트 탐색의 비효율성으로 인해서 정답 처리가 되지 않는다.

 

따라서 이를 해결해주기 위해서 해시 구조를 사용하여 풀어주어야만 한다.

 

나는 이를 풀기 위해 첫번째로 참가자 딕셔너리(part_dict)에 선수 이름과 선수의 숫자를 저장하고, 완주자 딕셔너리(comp_dict)에 선수 이름과 선수 숫자를 저장한 후 comp_dict에 없는 part_dict 이름을 리턴하거나, 또는 part_dict 에서의 참가자의 수가 comp_dict의 참가자의 수보다 큰 경우 그 이름을 리턴하는 방식으로 해결했다. (아래 코드에서 코드 1 참고하시면 됩니다.)

 

하지만 이 방법보다 더 효율적인 방식이 있었다. 결과적으로 딕셔너리 구조가 아니라 아예 "해시"를 적극 활용하는 방법이었다.

 

방법을 간단하게 설명하자면, 참가자의 이름을 hash로 변환하고, 이 hash를 key로 하여 이름을 value로써 딕셔너리에 저장해준다. 그리고 참가자의 hash 값을 하나하나 더해주고, 마지막에 완주자를 비교할 때, 완주자의 hash 값을 하나하나 빼주면 결과적으로 완주하지 못한 한명의 선수의 hash값이 나오게 된다.

 

그리고 이 hash값에 해당하는 이름을 출력해주면 완주하지 못한 참가자의 이름을 얻을 수 있게 된다. (코드 2 참고)

 

 

 

 

코드

 

코드 1

def solution(participant, completion):
    answer = ''
    comp_dict = {}
    part_dict = {}
    
    for _ in range(len(completion)):
        comp = completion.pop()
        if comp not in comp_dict.keys():
            comp_dict[comp] = 1
        else:
            comp_dict[comp] += 1
    
    for _ in range(len(participant)):
        part = participant.pop()
        if part not in part_dict.keys():
            part_dict[part] = 1
        else:
            part_dict[part] += 1
    
    for part in part_dict.keys():
        if part not in comp_dict.keys():
            return part
        else:
            if (comp_dict[part] - part_dict[part] < 0):
                return part

 

코드 2

def solution(participant, completion):
    answer = ''
    hash_dict = {}
    sum_hash = 0
    
    for part in participant:
        hash_dict[hash(part)] = part
        sum_hash += hash(part)
    
    for comp in completion:
        sum_hash -= hash(comp)
    
    answer = hash_dict[sum_hash]
    return answer

 

 

결과

 

 

코드 1

 

코드 2

 

결과적으로 해시를 적극적으로 활용하였을 때 아래와 같이 50% 이상 더 효율적인 결과를 얻을 수 있었다.