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

문제

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

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

제한 조건

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

나의 풀이:

def solution(participant, completion):
    for i in participant:
		    if i not in completion:
		        return i

가장 먼저 푼 방법이지만 완주하지 못한 사람이 동명이인인 경우 찾지 못한다.

def solution(participant, completion):
    for i in completion:
        if i in participant:
            participant.pop(participant.index(i))
    return participant[0]

동명이인을 걸러내기 위해 생각나는 대로 작성한 두번째 코드. 하지만 이 경우 모든 completion의 값 i를 모든 participant 값과 비교하고 제거해야되기 때문에 효율성이 너무 떨어진다.

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for idx, name in enumerate(completion):
        if participant[idx] != name:
            return participant[idx]
    return participant[-1]

in 연산자를 사용하지 않기 위해 participant와 completion을 모두 정렬해준 뒤 값이 다른 위치의 인덱스를 사용하는 방식으로 재구성했다. 이 때 완주하지 못한 사람이 리스트의 가장 끝에 있는 경우 for문을 통해 정답을 찾지 못하는데 이 경우에는 그냥 리스트 마지막 값이 정답이기 때문에 participant[-1]의 값을 반환하도록 했다.

다른 사람들의 풀이:

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for p, c in zip(participant, completion):
        if p != c:
            return p
    return participant[-1]

비슷하지만 살짝 다른 방식으로 zip 함수를 사용해서 문제를 풀 수도 있었다.

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

그리고 아직 공부를 하진 못했지만 원래 문제 의도는 해시를 사용해야하는 것이었나보다. 추후에 해시 공부를 한 뒤 다시 풀어보자.