프로그래머스 / 코딩 테스트 / 완주하지 못한 선수

문제 설명

 

 

문제 해결

 

hash를 사용해본 적이 없어서 다른 해결 방법을 고민해봤다.

 

"한 명의 선수"를 제외하고는 다 완주했다.

동명이인이 있을 수도 있다.

완주자 명단과 참가자 명단의 크기 차이는 1이다.

 

명단들을 같은 기준으로 정렬하고 각 원소들을 비교한다.

명단이 같은 기준으로 정렬되었기 때문에, 동명이인이나 누락되지 않는 한 각 원소들의 위치는 똑같을 것이다.

 

 

맨 마지막에 동명이인이나 누락자가 있을 수도 있으니까 리스트를 다 순회하고도 return문에 접근하지 않으면

참가자의 마지막 원소를 반환한다.

 

def solve(participant, completion): 
    
    participant = sorted(participant)
    completion = sorted(completion)
    
    for i in range(len(completion)): 
        if participant[i] != completion[i]: 
            return participant[i] 
        
    return participant[len(completion)]
    
def solution(participant, completion):
    answer = solve(participant, completion)
    return answer

 

다른 사람의 문제 해결

 

일단 hash가 무엇인지 알아야한다.

 

[자료구조/알고리즘] 해시(Hash) 란?

 

hash를 사용하면 특정 key에 대해서 거의 unique한 value를 얻어낼 수 있다.(충돌이 일어날 수 있지만)

python에서도 built-in으로 hash 함수가 존재했다.

 

Built-in Functions — Python 3.9.1 documentation

 

key를 참가자 이름을 해시한 값으로 value를 참가자 이름으로 구성하여 딕셔너리 변수의 데이터를 채우고

 

temp에 각 참가자 이름을 해시한 값을 누적시킨다.

 

완주자 이름을 해시한 값을 누적시킨 값에서 차감시켜서 마지막으로 남은 temp값은 완주하지 못한 사람의 이름이므로

딕셔너리를 검색하여 문자열로 반환한다.

 

출제자의 의도대로 잘 해결한 코드라고 생각한다.

 

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

    return answer