[Programmers] 완주하지 못한 선수 (Python 3)

문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다.

 

자꾸 머리 쓰니까 재밌다. ㅎㅎ 계속 풀게 된다

 

 

풀이

def solution(participant, completion):
    participant.sort()
    completion.sort()
    
    for i,v in enumerate(participant):
        try:
            if v != completion[i]:
                return v
        except IndexError:
            return v

 

참가자 배열과 완주자 배열 모두 오름차순 정렬한 후, 인덱스 당 요소가 모두 같은지 비교하는 방식을 썼다.

단 완주자 배열은 참가자 배열보다 인덱스가 1만큼 부족하기 때문에, 만약 정렬 후 마지막 참가자가 정답일 경우에 index error를 뱉게 된다.

try-except 문으로 묶어서 이 경우도 정답으로 처리할 수 있게끔 했다.

 

---

다른 사람의 풀이도 몇 봤는데, 참 재밌는 풀이가 많았다

 

다른 사람의 풀이 - 1

- collections 모듈의 Counter 객체를 이용한 방식

import collections

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

 

숏코딩은 참 볼 수록 마음이 편안해진다.

아마 출제의도에 부합한 방식은 아닌거 같으나, 가장 효율적인 풀이였다고 생각한다.

두 배열 중 교집합, 차집합 등등을 구할 때 Counter 객체가 유용한 것 같다. 꼭 써봐야지

 

 

다른 사람의 풀이 - 2

- hash를 이용한 방식

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

    return answer

 

진짜.. 창의적이다. 이런 식으로 접근이 가능할거라고는 상상도 못했다.

가장 효율적인건 아닐지 몰라도.. 출제자가 가장 미소지으면서 볼 풀이 아닐까

물론 경우의 수가 복잡한 문제가 아니었고, 비교 대상이 단 한명이라 가능한 풀이기도 하다. 해쉬 충돌 문제도 있다.

그치만 이런 접근법을 배워나가야 한다고 생각한다.