완주하지 못한 선수 (Python)

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

from collections import Counter


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

 

Level 1 문제라 그런지 코드가 매우 짧다. 파이썬으로 이 문제를 푸는 방법은 두 가지가 있다. 완전탐색, 그리고 딕셔너리끼리의 뺄셈.

 

완전탐색은 for문 안에 if ~ in 문을 넣어서 풀면 된다.

for c in completion:
    if c in participant:
        participant.remove(c)
return participant[0]

participant는 참가자 전원의 리스트이고 completion은 완주한 선수들의 리스트이다. participant보다 한 명이 적다.

졸려서 그랬는지 처음에는 participant를 순회하려고 했다. 그렇게 하면 participant를 순회하는 도중에 participant에서 remove를 하게 되어 에러가 발생한다. 리스트를 순회하는 도중에 값의 변경이 일어나면 안되기 때문이다.

대신에, completion을 순회하면서 그 값이 participant에 존재하면 participant에서 remove해주는 방식으로 해야 한다.

즉, 완주한 선수들의 이름을 하나씩 부르면서 참가자 전원 리스트에서 하나씩 소거해 나가는 것이다.

완주한 선수들의 이름을 모두 다 불렀는데도 참가자 리스트에 남아있는 선수가 바로 완주하지 못한 선수가 된다.

아무튼 설명이 길었지만 결론은 완전탐색 방식으로 하면 시간이 O(n^2)이 걸리게 되어 시간초과가 난다.

 

그럼 어떻게 해야 할까? 파이썬에서는 collections 모듈에서 Counter 함수를 제공한다.

Counter 함수에는 여러가지 사용법이 있는데, 매개변수로 리스트를 넣어주면 {값: 갯수}의 형태의 딕셔너리를 반환한다.

ex) collections.Counter(["leo", "kiki", "eden"]) ----> {"leo": 1, "kiki": 1, "eden": 1}

 

중요한 점이 여기서 등장한다. 원래 파이썬에서 set과는 달리 딕셔너리끼리 뺄셈을 지원하지 않는다.

그런데 Counter로 반환된 딕셔너리 모양의 오브젝트끼리는 더하기, 빼기, 차집합, 합집합이 가능하다.

따라서, 참가자 전원 Counter에서 완주한 선수 Counter를 빼 주면 이름이 중복되는 선수까지 다 계산해서 최종적으로 완주하지 못한 선수가 리턴된다.

맨 처음에 올린 코드처럼!

 

Counter 개념을 익혀놓자.