프로그래머스 "완주하지 못한 선수" [알고리즘/해쉬/코딩테스트 연습/파이썬(python)]

https://programmers.co.kr/learn/courses/30/parts/12077

프로그래머스

 

[ 문제 ]

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

[ 제한사항 ]

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

[ 알고리즘 설명 ] 

participant와 completion을 알파벳 순으로 정렬한다.

for문을 이용해서 처음부터 확인을 하는데, 마지막까지 다른 것을 찾지 못하거나, 중간에 다른 이름을 찾는다면 그 이름을 리턴한다.

 

해시를 사용해야하는 문제인데, 리스트만으로 풀 수 있을 것 같아서 리스트만을 이용한 것, 딕셔너리를 이용한 방법을 풀어보았다. 생각한 알고리즘이 똑같아서 그런지 코드는 똑같다.

딕셔너리는 내부적으로 해시함수가 사용되기 때문에, 해시를 이용해서 푼 것이다.

 

#그냥 리스트로 풀이
def solution(participant, completion):
    participant.sort()
    completion.sort()
    
    for i in range(len(participant)):
        if i == len(participant)-1 or participant[i] != completion[i]:
            return participant[i]

 

#딕셔너리(해쉬) 사용해서 풀이
def solution(participant, completion):
    participant.sort()
    completion.sort()
    last = len(participant) -1
    p = dict()
    c = dict()
    for i in range(last):
        p[i] = participant[i]
        c[i] = completion[i]
    p[last] = participant[-1]

    for i in range(last+1):
        if i == last or p[i] != c[i]:
            return p[i]