[Python] Lv1. 완주하지 못한 선수

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

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

 

 

 

 

 

문제 설명

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

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

 

 

제한사항

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

 

나의 접근 방법 및 알고리즘

for() 문과 if() 문을 이용해서 participant 속 참가자가 완주한 참가자 배열 completion에 존재한다면 completion에서 remove()를 이용해서 지우고, 만약 존재하지 않는다면 answer에 문자를 추가하여 return 하도록 했다. 

하지만, 일부 테스트에서 시간초과로 실패했다.

def solution(participant, completion):
    answer = ''
    for p in participant:
        if p in completion:
            completion.remove(p)
        else:
            answer += p
            break       
    return answer

 

def solution(participant, completion):
    answer = ''
    participant.sort()
    completion.sort()

    for i in range(len(completion)):    
        if (participant[i] != completion[i]):   #비교했을 때 없으면 그게 바로 미완주자
            return participant[i]

    return participant[-1]      ## participant의 마지막사람이 미완주자일경우

 

다른 풀이

import collections

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

Counter 객체끼리를 뺄셈이 가능하다는 점을 이용한 풀이이다. 그런데 이 경우에는 모든 참가자의 경우를 다 탐색해야 하기 때문에, for() 문을 이용하여 바로 리턴하는 것보다 시간이 더 걸린다는 단점이 있다.

 

def solution(participant, completion):
    hashDict = {}
    sumHash = 0

    for part in participant:
        hashDict[hash(part)] = part
        sumHash += hash(part)

    for comp in completion:
        sumHash -= hash(comp)
        
    return hashDict[sumHash]
print(solution(["marina", "josipa", "nikola", "vinko", "filipa"] , 
["josipa", "filipa", "marina", "nikola"]))

: 해시를 이용한 경우이다.

participant에서 참여자를 hash한 값을 key, 참여자는 value로 만든다.  그리고 sumHash에 participant의 key값을 모두 더한다.

completion에서 참여자를 hash 한 값을 sumHash에서 뺀다. 이게 가능한 이유는 해시! 같은 이름에 대한 해시값은 같기 때문이다. 이렇게 빼면 결국 미완주자인 한 명만의 해시값 즉, key 값이 남게 된다.

우리는 미완주자의 이름을 return 하기 위해 hashDict에서 sumHahs, 남은 한 명의 key값으로 value값을, 즉 미완주자의 이름을 최종적으로 return 하게 된다.