[Python] 프로그래머스 Hash Lv.1 완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return하도록 solution 함수를 작성해주세요.

 

단순하게 반복문으로 participant에서 참여자 명을 하나씩 불러와 해당 이름이 완주자 명단(completion)에 있다면 명단에서 지우고 위의 작업을 반복해 더이상 완주자 명단에 없는 이름이 나올 경우 해당 이름을 return 하는 코드를 만들었다.

 

정확성은 통과했지만 효율성 테이스에서 시간 초과로 실패가 떠서 오답처리가 되었다.

#효율성 테스트 실패(시간 초과)

def solution(participant, completion):
    for i in participant:
        if i in completion:
            completion.remove(i)
        else:
            return i

 

구글링을 통해 알아본 결과 크게 Sort 정렬과 Hash를 이용해 푸는 방법이 있다.

문제가 의도한 바로는 Hash를 이용하는 코드가 더 적절한 방법이다.

 

1. Sort 정렬

먼저 participant와 completion의 요소들을 정렬(sort)해준다.

for 반복문으로 완주자 배열(completion)의 길이(len)만큼 i를 불러와 두 리스트를 비교한다.

participant의 i번째 요소와 completion의 i번째 요소가 다를 경우 해당하는 participant의 요소를 return하고,

completion의 길이만큼 반복문을 다 돌아도 조건에 해당하는 경우가 없으면 participant의 마지막[-1] 요소를 return 한다.

#Sort 정렬을 이용한 코드

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        if participant[i]!=completion[i]:
            return participant[i]
    return participant[-1]

 

2. Hash

먼저 비어있는 해시 테이블 hashdict = {} 과 해시 값을 더해줄 변수 sumhash를 만들어준다.

다음으로 participant의 요소들을 반복문으로 하나씩 불러와 hashdict에 저장하는데 key 값은 불러온 요소의 hash 값이다.

sumhash에는 불러온 요소들의 hash 값들을 모두 더해준다.

그리고 completion의 요소를 하나씩 불러와 sumhash에서 completion 요소들의 해시값을 하나씩 빼준다.

위의 과정을 모두 반복하고 남은 hash값을 key값으로 가진 value가 완주하지 못한 선수의 이름이다.

 

* hash() 함수는 객체의 해시값을 반환한다.

#Hash 값을 이용한 코드

def solution(participant, completion):
    hashdict = {}
    sumhash = 0

    for p in participant:
        hashdict[hash(p)] = p
        sumhash += hash(p)

    for c in completion:
        sumhash -= hash(c)

    return hashdict[sumhash]

 

프로그래머스