[Algorithm] 프로그래머스 - 완주하지 못한 선수

시작하며...

모든 알고리즘 문제 풀이는 제가 직접 짜서 정답을 맞춘 결과만을 공유합니다.

마지막 'More Solution'은 다른 정답자들 풀이 중 생각지 못했던 부분들이나 좋게 느껴진 풀이법 몇개를 가져와서 공유하였습니다.

 

[Level 1] 완주하지 못한 선수

프로그래머스

 

문제 설명

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

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

제한사항

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

입출력 예

입출력 예 설명

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

My Solution

def solution(participant, completion):

    # for i in completion:
    #     participant.remove(i)
    # return participant[0]
    # for i in participant:
    #     if (participant.count(i) != completion.count(i)) or (i not in completion):
    #         return i
    
    dic = {}
    for p in participant:
        if p not in dic: # key
            dic[p] = 0
        dic[p] += 1
    for c in completion:
        dic[c] -= 1
        if dic[c] == 0:
            del dic[c]
    return list(dic.keys())[0]

 

이 문제는 Hash 자료구조를 이용하여 풀이하여야 한다. 주석 처리된 풀이처럼 List를 이용하여 문제를 풀면, 정확성 테스트는 넘어가지만 효율성 테스트를 넘지 못한다. 파이썬은 딕셔너리가 해시구조이므로 딕셔너리를 이용하여 문제를 풀이했다.

해시에 대한 자세한 내용은 아래 포스팅에서 정리해두었다. 문제 풀이에 대한 내용도 포함되어있다.

[Python] 자료구조 : Hash

• 참가자 participant의 수만큼 반복문을 돌면서 참가자를 딕셔너리에 Key로 추가하고 value값은 추가될때마다 1씩 올려준다.
• 만약 참가자 p가 dictionary 변수 dic에 없다면 새로운 key로 추가하고 value는 0으로 초기화
• 그리고 참가자 추가가 끝나면 완주한 사람 completion에서 같은 키값으로 dic에서 value를 하나씩 줄이면서 반복문을 돌려준다.
• 최종적으로는 완주하지 못한 한 사람의 이름인 key 와 value가 1로 남아있게된다.
• 남은 값의 key를 가져와서 리턴하면 완주하지 못한 한 사람이 나온다.

 

More Solution

from collections import Counter
def solution(participant, completion):
    p_ = Counter(participant)
    c_ = Counter(completion)
    cnt = p_ - c_
    
    return list(cnt)[0]

위와 같이 해시를 이용한 풀이인데 파이썬에서는 collections 모듈을 이용하면 더 쉽게 풀이할 수 있었다.