[Programmers] 프로그래머스 완주하지 못한 선수 with Python

Description

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

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

제한사항

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

입출력 예

participant	completion	return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

---

성공한 코드

def solution(participant, completion):
    dict = {}
    for x in participant:
        dict[x] = 0
    for x in participant:
        dict[x] += 1
    for x in completion:
        dict[x] -= 1  
    s_dict = sorted(dict.items(), key=lambda x: -x[1])
    answer = s_dict[0][0]
    return answer

딕셔너리 자료형을 이용해서 코드를 짜보았다. 중복되는 단어를 따로 체크하기 위해 단어의 등장 수만큼 value 카운팅을 늘리는 방법을 사용했다. 반대로 completion에 등장하는 단어를 다시 1씩 빼주면, 결과적으로 dictionary에는 value가 1인 item이 하나밖에 남지 않게 된다. 그 단어를 출력하기 위해 value 값을 기준으로 내림차순 정렬을 한 후 첫번째 튜플의 첫번째 값을 인덱싱하였다. 

 

실패한 코드

def solution(participant, completion):
    for x in completion:
        if x in participant:
            participant.remove(x)
    answer = participant[0]
    return answer

맨 처음 문제를 보고 간단하게 짜 본 코드이다. 뭐지 이렇게 쉽게 짜져도 되나 싶었는데 역시나 시간초과에 걸려버렸다. 

이렇게 짜면 답은 맞을 수 있으나, for 문 안에 remove 함수가 들어가 버려 시간복잡도가 증가한다. 내 입장에서 쓰기 편한 함수보다는 컴퓨터 입장에서 계산하기 편한 로직을 항상 고려하자.

 

다른 좋은 코드들

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

해쉬함수를 사용한 좋은 코드가 있어 가져와 보았다.

참가자 이름을 hash 함수로 변환한 해쉬값을 dictionary의 key로 놓고, 이름을 value로 저장한다. 그리고 그 hash값을 다 더한 변수를 생성한다. 두번째 for 문에서 competition을 돌면서 이 더한 값을 다시 빼주면 마지막 남은 값은 한 명의 해쉬값이 구해진다. 

 

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

또 다른 아이디어는 두 리스트를 1:1로 비교하는 것이다.

순서대로 비교하기 위해서 일단 두 리스트를  정렬하고 zip함수를 통해 변수 하나하나를 꺼내 확인한다. 만약에 두 이름이 다르다면 그 사람이 바로 완주한 한 사람이 된다. 아주 간단하고도 기발한 아이디어인 것 같다. 

 

 

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

프로그래머스