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

생각의 흐름

동명이인이 있을 수 있다는 것에 꽂혀서 set을 사용하려고 했다.

• participant와 completion의 set이 동일하지 않은 경우 두 집합의 차집합이 answer가 된다.
• set이 동일할 경우, for문을 통해 순회를 한다.
• 최악의 경우, O(NlogN)

풀이

# set이 다른 경우에는 차집합
# set이 같은 경우에는 for 문...?
def solution(participant, completion):
    if set(participant) != set(completion):
        answer = list(set(participant)-set(completion))[0]
    else:
        sorted_participant = sorted(participant)
        sorted_completion = sorted(completion)
        for i, p in enumerate(sorted_participant):
            if p != sorted_completion[i]:
                answer = p
                break
    return answer

헷갈렸던 지점

1. 차집합 계산이 for문 보다는 빠를 것이라고 생각하여 경우를 나누었다. 정말 그럴까?

• set의 차집합 시간복잡도를 검색해보니 O(len(t)-len(s))이다.....for문으로 한 번 순회하는 것과 그리 큰 차이가 나지 않는다.....🫥 그럼 그냥 처음부터 else 부분의 코드만 쓰는 게 나을 수도 있었겠다.

2. sorted 함수와 .sort() 메소드가 가끔씩 헷갈린다
   • sorted 함수는 return값으로 새로운 리스트를 내뱉는다고 기억해두자!

다른 코드 보고 배운 점

collections 모듈의 collections.Counter 라는 것을 사용한 분들이 많았다.

Counter란?

dict subclass for counting hashable objects
hash로 표현 가능한 object들의 개수를 세기 위한 dictionary 의 서브클래스이다.
다시 말해, 주어진 데이터의 요소들의 개수를 셀 때 매우 편리한 클래스이다. hash 관련 문제를 풀 때 많이 사용하는 것 같다.

Counter라는 클래스의 좋은 점은 덧셈 뺄셈 연산이 가능하다는 것이다!

import collections

c1 = collections.Counter(['바나나', '호랑이', '호랑이'])
c2 = collections.Counter(['바나나', '호랑이'])

c1-c2 #Counter({'호랑이':1})

key, value값은 dic처럼 다루면 된다.

이 클래스를 사용하면 코드가 훨씬 간결해지고, hash 출제 의도에 맞는 코드를 작성할 수 있다.