count를 영리하게

리스트에 있는 원소의 개수를 각각 카운팅 해야하는 상황이 있다. 내가 택했던 방법은

 

nums = list(map(int, input().split()))
num_set = set(nums)
counts = dict()
for num in num_set:
    counts[num] = nums.count(num)

set을 구한 뒤, list에서 set을 count하는 형태였다. 근데 자꾸 시간초과가 나서 설마 이것 때문인가 하고 찾아보니

def list_to_set(l):
    s = set()
    # Repeat n times --> O(n)
    for x in l:
        # Add element to set --> O(1)
        s.add(x)
        
    return s

리스트 -> set으로 변환을 할 때에는, 일단 set을 선언한 뒤 리스트의 모든 원소를 때려박는 형태였던 것이다...

그러니 여기서 O(n)의 시간복잡도를 형성한다...

그 후 set의 모든 원소에 대해서 list에 count하니 set의 길이 * O(n)의 시간복잡도를 추가로 형성한다...

 

검색을 통해서 좋은 코드를 찾아보았다.

nums = list(map(int, input().split()))
counts = dict()
for num in nums:
    try:
        counts[num] += 1
    except:
        counts[num] = 0

카운트 후 딕셔너리를 만들기 까지 O(n)의 시간복잡도를 한번 형성한다.

정말 깔끔하고 잘 짰다고 생각되는 코드다.

 

반성하자.