[프로그래머스] 완주하지 못한 선수(python)

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

프로그래머스

📌 문제 설명

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

마라톤에 참여한 선수들의 이름이 담긴 배열 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"

✔️ 입출력 예 설명

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

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

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

---

🗒 풀이

import collections

def solution(participant, completion):
    answer = collections.defaultdict(int)
    for par in participant:
        answer[par] += 1

    for com in completion:
        answer[com] -= 1

    for ans in answer:
        if answer[ans] > 0:
            return ans

파이썬에서 제공하는 collections 모듈의 defaultdict를 사용한다. 이를 사용함은 생성 시 키에 해당하는 값으로 collections.defaultdict(type)의 type을 기반으로 초기 형태를 잡아주기 때문이다. 위의 코드에서는 int를 type값으로 넣어놨기에 초기 키값이 0으로 되어있을 것이다. 때문에 첫번째 for문에서 participant의 키값에 바로 1을 증가해도 오류가 나지 않는다.

만약 defaultdict이 아닌 그냥 {} 형태로 딕셔너리를 만든다면 저 코드에서 오류가 날 것이다.

참가자들 이름으로 딕셔너리를 만들고, 1을 증가해주는 것은 참가자들의 중복을 확인하기 위함이다.

다음 completion을 for문으로 돌면서 만들어놓은 answer 딕셔너리에 해당하는 값을 1씩 감소한다.

 

처리를 다 했다면, 마지막으로 answer 딕셔너리를 돌면서 확인한다. 만약 0보다 값이 많은 경우는 completion을 하지 못해 1을 감소하지 못한, 즉 완주하지 못한 선수들이므로 바로 return 해주면 된다.

 

---

🤔 후기

간단한 문제였는데도 나름 시행착오를 많이 겪었다.

 

일단 테스트케이스를 제대로 보지 않은채, 중복된 값만 지우면 되지 않나?라는 생각에 차집합을 사용하기로 했다.

def solution(participant, completion):
    participant = set(participant)
    completion = set(completion)
    answer = participant.difference(completion)    # participant - completion
    return list(answer)[0]

테스트케이스 1, 2는 통과했으나 중복된 값이 있던 테스트케이스 3에서 오류가 났다.

참여자 명단에 이름이 중복된 선수들이 있었고, 완주자는 그 선수들 중 한 명밖에 없었다. 내 코드는 중복된 것은 고려하지 않은 채 교집합을 제거하는데 집중한 것이었다.

 

중복된 값을 고려하며 다시 코드를 짰다.

def solution(participant, completion):
    answer = participant.copy()
    for com in completion:
        if com in answer:
            answer.remove(com)

    return answer[0]

테스트 케이스는 다 통과를 했다. 하지만 역시 효율성에서 막혔다. 순차적으로 completion과 participant(answer이 이를 copy했기에 participant를 돌았다고 보자)를 접근하기에 효율성면에서 좋지 않을 수 밖에 없었다.

 

다른 사람들 답을 볼까 말까 하던 차에...위에 문제 분류가 보였다.

답은 해시였다.

덕분에 잘 풀 수 있었다.

 

---

다른 사람의 풀이 중 이런 방법도 있었다.

 

Counter 객체를 사용하는 것이다.

import collections


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

 

또 이 풀이도 해시함수를 사용했는데, 이게 진짜 출제자가 원한 해시 사용인 것 같다.

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