세어보자! 딕셔너리와 집합

안녕, 나 코딩냥이다냥! 지난 시간에 정렬을 배웠지? 정렬은 강력하지만 줄을 세우는 값이 있다냥. 오늘은 줄을 세우지 않고도 답을 찾는 방법을 배운다냥. 그리고 이건 정렬보다 빠르다냥.

오늘의 학습 목표

딕셔너리로 "무엇이 몇 개인지" 센다.
집합으로 "이미 본 적 있는지" 기억한다.
딕셔너리에서 가장 큰 값의 열쇠를 찾는다.
정렬보다 빠른 이유를 횟수로 설명할 수 있다.

1단계 · 리스트로 세면 왜 느리냥 (7분)

"banana" 에서 각 글자가 몇 번 나오는지 세어보자냥. 지금까지 배운 걸로만 하면 이렇게 된다냥.

word = "banana"
letters = []
counts = []

for ch in word:
    if ch in letters:
        counts[letters.index(ch)] += 1
    else:
        letters.append(ch)
        counts.append(1)

이 코드의 문제는 ch in letters 라냥.

파이썬이 이 한 줄을 처리하려면 리스트를 처음부터 끝까지 훑어야 한다냥. 글자 하나를 볼 때마다 그동안 모은 글자를 전부 다시 훑는 거라냥.

글자가 늘어나면 훑는 횟수가 곱절로 늘어난다냥.

2단계 · 딕셔너리는 바로 찾는다냥 (10분)

딕셔너리는 열쇠(key)로 바로 꺼내는 상자라냥. 훑지 않고 한 번에 간다냥.

비유로 이해하기 — 사물함

리스트에서 찾기	딕셔너리에서 찾기
1번 칸부터 순서대로 열어본다	이름표를 보고 바로 그 칸으로 간다
칸이 100개면 최대 100번	칸이 100개여도 한 번
뒤에 있을수록 오래 걸린다	어디 있든 똑같이 빠르다

이게 오늘 배우는 것의 핵심이라냥. 찾는 데 훑지 않는다냥.

word = "banana"
count = {}                  # 빈 딕셔너리

for ch in word:
    if ch in count:
        count[ch] += 1
    else:
        count[ch] = 1

print(count)                # {'b': 1, 'a': 3, 'n': 2}

더 짧게 쓰는 법

count = {}
for ch in word:
    count[ch] = count.get(ch, 0) + 1

해설get(ch, 0) 이 하는 일

count.get(ch, 0) 은 "있으면 그 값, 없으면 0" 이라는 뜻이라냥.

없을 때를 따로 처리하는 if 를 없애준다냥. 세는 코드는 거의 항상 이 모양으로 쓰니까 통째로 외워두면 편하다냥.

3단계 · 집합은 "본 적 있냥?"만 기억한다냥 (7분)

개수는 필요 없고 봤는지 안 봤는지만 알면 될 때가 있다냥. 그럴 땐 집합이 더 알맞다냥.

arr = [3, 1, 4, 1, 5]
seen = set()                # 빈 집합

for x in arr:
    if x in seen:
        print("처음 중복:", x)   # 1
        break
    seen.add(x)

집합도 딕셔너리처럼 훑지 않고 바로 확인한다냥. x in seen 은 집합이 아무리 커져도 빠르다냥.

차이는 이것뿐이라냥 — 딕셔너리는 열쇠와 값을 같이 담고, 집합은 열쇠만 담는다냥.

빈 집합은 set() 이라고 써야 한다냥.

{} 라고 쓰면 빈 딕셔너리가 만들어진다냥. 헷갈리기 쉬운 부분이라냥.

4단계 · 가장 많이 나온 것 찾기 (10분)

센 다음에는 보통 제일 많은 것을 찾게 된다냥. 여기 함정이 하나 있다냥.

count = {'b': 1, 'a': 3, 'n': 2}

print(max(count, key=count.get))    # a

해설max 에 key 를 주면

max(count) 라고만 쓰면 열쇠끼리 비교해서 'n' 이 나온다냥. 우리가 원한 게 아니라냥.

key=count.get 을 주면 각 열쇠의 값으로 비교한다냥. 지난 시간 정렬에서 배운 key= 와 완전히 같은 개념이라냥.

동점일 때는?

"bbaa" 를 세면 {'b': 2, 'a': 2} 라냥. 둘 다 2번이라냥.

이때 max() 는 먼저 나온 것을 돌려준다냥. 즉 'b' 라냥.

그런데 문제가 "동점이면 사전순으로 앞선 글자"를 요구하면 답은 'a' 라냥. 이렇게 쓰면 된다냥.

print(min(count, key=lambda ch: (-count[ch], ch)))

-count[ch] 로 많은 것이 앞에 오게 하고, 동점이면 ch 로 사전순 비교한다냥. 지난 시간에 배운 튜플 키가 여기서 또 쓰인다냥.

5단계 · 왜 빠르냥 — 횟수로 보기 (7분)

첫 시간에 "한 번만 훑으면 빠르다, 훑는 안에서 또 훑으면 느려진다"고 했지? 오늘 그 말의 뜻이 완성된다냥.

원소가 n개일 때 대략 몇 번 보냐

방법	보는 횟수	이름
리스트로 세기	n × n	O(n²)
정렬한 뒤 세기	n × log n	O(n log n)
딕셔너리로 세기	n	O(n)

첫 줄이 느린 건 in 으로 확인할 때마다 리스트를 처음부터 훑기 때문이라냥.

n이 10이면 셋 다 순식간이라냥. 그런데 n이 10만이면? 100억 번 / 170만 번 / 10만 번 이라냥. 하늘과 땅 차이라냥.

기억할 것세는 문제는 먼저 딕셔너리를 떠올리자냥

"무엇이 몇 개냐", "중복이 있냐", "짝이 있냐" 같은 문제를 만나면 정렬보다 먼저 딕셔너리와 집합을 떠올리는 습관을 들이자냥.

정렬이 필요한 순간은 순서가 필요할 때라냥. 개수만 필요하면 줄을 세울 이유가 없다냥.

오늘 배운 내용 정리

먼저 스스로 답해보고, "정답 보기"를 눌러서 맞는지 확인해보자냥!

count[ch] = count.get(ch, 0) + 1 은 무슨 뜻이냥?

빈 집합을 만들려면 어떻게 쓰냥?

max(count) 와 max(count, key=count.get) 은 뭐가 다르냥?

동점일 때 사전순으로 앞선 것을 고르려면?

개수를 셀 때 딕셔너리가 리스트보다 빠른 이유가 뭐냥?

이제 직접 풀어볼 차례다냥

오늘도 medium 다섯 문제라냥. 앞의 셋은 세는 연습이고, 4번과 5번은 정렬로도 풀리지만 딕셔너리가 더 빠른 문제라냥. 두 방법을 다 떠올려보고 왜 딕셔너리가 나은지 생각하면서 풀어보자냥. 가보자냥~