[프로그래머스] Level1 | 완주하지 못한 선수 - 파이썬(Python) | 해시(Hash)

https://programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

 

프로그래머스 Level1에서 "완주하지 못한 선수" 문제를 풀었다.

 

문제 설명

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

 

제한 사항

- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.

- completion의 길이는 participant의 길이보다 1 작습니다.

- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

- 참가자 중에는 동명이인이 있을 수 있습니다.

 

처음 시도했던 방식은 아래와 같다.

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

participant와 completion을 비교하기 위해 먼저 정렬을 해 주었다.

completion의 길이가 participant보다 짧기 때문에 append를 해주었는데 이는 아래 for문을 정상적으로 돌리기 위해 길이를 맞춰준 것이다. 실행은 잘 됐지만 동명이인인 경우를 생각을 하지 못했다. 

당연히 동명이인에 해당하는 테스트 케이스 실패가 떴고 해당 문제가 해시를 이용한 문제라는 것을 알게 되어 해시를 어떻게 사용했는지 다른 사람들의 코드를 찾아보면서 공부를 했다.

 

다른 사람 풀이를 참고하며 작성한 코드는 아래와 같다.

def solution(participant, competion) :
    answer = ''
    temp = 0
    dic = {}
    
    for part in participant :
        dic[hash(part)] = part   #dictionary에 key(hash값)-value(이름) 쌍을 추가, key 값은 중복 허용 안됨.
        temp += int(hash(part))  #hash값 중첩시킴
        
    for com in competion :
        temp -= hash(com)    #value에 대한 hash값을 제거해서 도착 안한 사람의 hash의 key값만 남음
        
    answer = dic[temp]
    
    return answer

key 값은 중복 허용이 안되기 때문에 위에서 내가 해결하지 못한 동명이인의 문제를 해결할 수 있었다.

dictionary를 사용해서 key에 hash값을 넣을 수도 있다는 것을 배우게 되었다.

위에서 내가 짠 for문으로 원소들을 1:1로 비교하며 같은지 파악하는 방법보다 이렇게 hash값을 제거하며 도착 안 한 사람의 hash의 key를 남기는 것이 더 효율적이라는 것도 알게 되었다!

 

해당 문제 풀이 코드

깃허브에 풀이 코드를 함께 업로드 해 두었으니 구경오세유~

 

---

알고리즘 공부를 해야지 해야지 말만 하다가 아이펠 후반기 풀잎이 열리면서 본격적으로 공부를 하게 되었는데,

이코테 교재로 개념 공부만 하다가 이렇게 직접 프로그래머스로 풀어보니 한참 부족하다고 생각했다.

정말 열심히 코테 연습 해야겠다 ㅠ...