해시 - 세기와 찾기를 빠르게

이 장에서 배우는 것

앞 장에서 스택과 큐는 자료가 들어오고 나가는 순서를 기억했다. 이번에는 순서보다 “이 값이 있었는가”, “몇 번 나왔는가”가 중요한 문제를 다룬다. 리스트를 처음부터 훑어도 답을 구할 수 있지만, 같은 질문을 반복하면 이미 확인한 자료를 거듭 읽게 된다. 해시(hash)는 값을 찾기 위한 단서를 계산해 탐색 범위를 줄이는 방법이다. 파이썬의 딕셔너리와 집합은 이 방법을 활용한다.

이 장에서는 택배 표식의 빈도를 세고, 두 포장 묶음의 무게를 맞춘 뒤, 마지막으로 재고 변동 기록에서 합이 정해진 값인 연속 구간의 개수를 구한다. 도구 사용법에서 출발하되, 어떤 정보를 저장해야 다음 질문에 바로 답할 수 있는지에 초점을 둔다.

• dict, set, Counter를 질문의 종류에 맞게 선택한다.
• 두 수의 합 문제에서 필요한 상대 값을 계산하고, 같은 원소를 두 번 쓰지 않도록 처리한다.
• 누적 합의 차이를 이용해 구간 합 문제를 이전 값의 빈도 조회로 바꾼다.
• 해시 충돌과 평균 시간 복잡도의 의미를 구분한다.
• 작은 입력을 빠짐없이 만들어 느린 풀이와 빠른 풀이를 대조한다.

문제 상황

작은 공동 창고에서 하루 동안 일어난 재고 변동을 순서대로 기록한다고 하자. 입고는 양수, 출고는 음수다. 담당자는 “연속한 몇 건의 기록을 묶었을 때 재고가 정확히 3만큼 늘어난 경우가 몇 개인가”를 확인하려 한다. 기록을 건너뛰거나 순서를 바꾸어 묶을 수는 없다. 같은 합을 만드는 구간이라도 시작 위치나 끝 위치가 다르면 따로 센다.

예시 기록은 [2, -1, 2, -2, 3, -1]이다. 첫 세 기록을 묶으면 합이 3이고, 다섯 번째 기록 하나만 골라도 합이 3이다. 전체 기록의 합도 3이다. 이처럼 구간의 길이는 일정하지 않다. 출고 기록 때문에 합이 증가하다가 감소할 수도 있으므로, 합이 커졌다는 이유만으로 특정 시작점을 버릴 근거도 아직 없다.

가장 직접적인 방법은 시작점과 끝점을 모두 고르는 것이다. 시작점을 고정하고 끝점을 오른쪽으로 한 칸씩 옮기면서 합을 갱신하면 모든 구간을 확인할 수 있다. 이 풀이는 느리지만 기준이 명확하다. 뒤에서 더 빠른 풀이를 만든 뒤에도 정답을 확인하는 비교 대상으로 남겨 둔다.

빠른 풀이를 곧바로 외우기 전에, 창고에서 나타나는 더 작은 질문 두 가지를 살펴본다. 표식이 몇 번 등장했는지 세는 질문과, 두 묶음의 무게가 목표를 이루는지 찾는 질문이다. 두 질문에서 저장할 정보를 정하는 방식이 마지막 문제로 이어진다.

값을 열쇠로 삼아 세고 찾기

택배 표식: 존재와 횟수는 다른 정보다

택배 표식이 ["나", "다", "나", "라", "다", "나"] 순서로 들어왔다고 하자. 표식 “나”를 본 적이 있는지만 묻는다면 집합이면 충분하다. 몇 번 보았는지 묻는다면 표식과 횟수를 연결해야 한다. 이때 딕셔너리의 키는 표식, 값은 횟수가 된다. 키 하나에는 현재 값 하나가 연결되므로 같은 키를 다시 대입하면 이전 값을 바꾼다.

labels = ["나", "다", "나", "라", "다", "나"]

seen = set(labels)

counts = {}
for label in labels:
    counts[label] = counts.get(label, 0) + 1

print("나" in seen)
print(counts["나"])
print(counts.get("마", 0))

get(label, 0)은 키가 있으면 연결된 값을, 없으면 기본값 0을 돌려준다. 처음 보는 표식에도 같은 갱신식을 쓸 수 있다. 반면 counts[label]로 없는 키를 읽으면 KeyError가 발생한다. 기본값을 쓰는 이유는 예외를 숨기려는 것이 아니라, 이 문제에서 “아직 보지 않은 표식의 횟수는 0”이라는 뜻을 코드에 담기 위해서다.

표식을 하나 처리할 때마다 해당 표식의 횟수만 늘어난다

처리 순서	표식	처리 뒤 횟수
1	나	나: 1
2	다	나: 1, 다: 1
3	나	나: 2, 다: 1
4	라	나: 2, 다: 1, 라: 1
5	다	나: 2, 다: 2, 라: 1
6	나	나: 3, 다: 2, 라: 1

반복문이 표식을 몇 개 처리한 직후에도 “각 키의 값은 지금까지 처리한 부분에서 그 표식이 나온 횟수다”라는 설명이 유지된다. 이를 불변식이라 한다. 처음에는 처리한 표식이 없으므로 빈 딕셔너리가 맞다. 다음 표식의 횟수만 1 늘리면 설명은 계속 맞고, 반복이 끝나면 전체 빈도표가 된다.

표식이 모두 n개이고 서로 다른 표식이 u개라면, 해시 조회와 갱신을 평균 상수 시간으로 볼 때 시간은 O(n), 빈도표 공간은 O(u)다. 집합도 중복을 없애므로 서로 다른 표식 수만큼 공간을 쓴다. 단, 집합으로 바꾼 뒤에는 원래 표식이 몇 번 나왔는지 복원할 수 없다.

횟수 세기가 목적이면 표준 라이브러리의 collections.Counter로 같은 의도를 짧게 나타낼 수 있다. Counter는 딕셔너리의 하위 클래스이며, 없는 키의 횟수를 대괄호로 읽으면 0을 돌려준다. 다음 코드는 “나”의 횟수로 3을, “마”의 횟수로 0을 출력한다.

from collections import Counter

counts = Counter(["나", "다", "나", "라", "다", "나"])
print(counts["나"])
print(counts["마"])

딕셔너리에서 x in counts는 키의 존재를 묻는다. 값들 사이에 x가 있는지 묻는 표현이 아니다. 또한 횟수를 0으로 바꾸어도 키가 자동으로 삭제되지는 않는다. 존재와 양의 횟수를 같은 뜻으로 취급하려면 자료를 갱신하는 규칙까지 함께 정해야 한다.

해시 충돌이 있어도 키를 구별한다

해시 테이블(hash table)은 키에서 해시값을 계산하고, 이를 이용해 저장하거나 찾을 위치의 후보를 정한다. 서로 다른 키가 같은 해시값을 갖거나 같은 위치 후보로 모이는 일을 해시 충돌이라 한다. 충돌이 생겼다는 이유로 두 키가 같은 키가 되는 것은 아니다. 구현은 필요한 후보를 더 조사하고 키의 동등성도 확인해 값을 구별한다.

그림은 충돌의 뜻을 설명하는 모형이다. 실제 파이썬 딕셔너리의 내부 칸 배치를 그대로 그린 것은 아니다. 여기서 기억할 결론은 두 가지다. 조회가 빠르도록 후보를 좁히지만, 모든 입력에서 언제나 한 번의 비교로 끝나는 것은 아니다. 따라서 딕셔너리와 집합의 조회를 O(1)이라고 말할 때는 보통 평균 비용을 뜻한다.

충돌이 심한 경우 한 번의 조회가 저장된 키 수에 비례하는 비용을 들일 수 있다. 이 장의 복잡도는 정수 키를 다루고 해시 연산의 평균 비용을 상수로 보는 일반적인 분석을 따른다. 아주 큰 정수의 자릿수에 따른 계산 비용까지 따지는 분석은 여기서 생략한다.

키는 저장된 동안 해시와 동등성 판단이 안정적으로 유지되어야 한다. 정수와 문자열은 키로 쓸 수 있지만, 내용을 바꿀 수 있는 리스트는 키로 쓸 수 없다. 여러 값을 묶어 키로 삼을 때는 원소도 해시 가능한 튜플을 사용할 수 있다. 딕셔너리는 삽입 순서를 보존하지만 집합에는 출력 순서를 기대하지 않는 편이 맞다. 정해진 순서의 출력을 원하면 정렬처럼 순서를 명시하는 과정이 필요하다.

두 수의 합을 이전 값 조회로 바꾸기

포장대에 무게가 [6, 4, 6, 9]인 묶음 네 개가 놓여 있다. 서로 다른 두 묶음을 골라 무게 합을 12로 만들고, 가능하면 두 위치를 돌려주는 문제를 생각하자. 위치는 0부터 센다. 모든 두 위치를 비교하면 O(n²)이지만, 현재 무게가 x라면 필요한 상대 무게는 12 - x 하나로 정해진다.

따라서 앞에서 본 무게와 그 위치를 딕셔너리에 저장한다. 현재 무게를 읽으면 먼저 상대 무게가 저장되어 있는지 확인한다. 있다면 저장된 위치와 현재 위치가 답이다. 없다면 현재 무게를 나중에 사용할 수 있도록 등록한다. 이 순서가 같은 묶음을 두 번 사용하는 일을 막는다.

현재 묶음을 등록하기 전에 필요한 상대 무게를 찾는다

현재 위치와 무게	필요한 무게	조회 전 저장 내용	판정
0번, 6	6	없음	없으므로 6의 위치를 저장
1번, 4	8	6: 0	없으므로 4의 위치를 저장
2번, 6	6	6: 0, 4: 1	0번과 2번을 반환

def find_pair(weights, target):
    positions = {}
    for i, weight in enumerate(weights):
        need = target - weight
        if need in positions:
            return positions[need], i
        if weight not in positions:
            positions[weight] = i
    return None

반복 시작 시점에 딕셔너리는 현재 위치보다 앞에 있는 무게의 위치만 담고 있다. 그러므로 찾은 상대는 현재 묶음과 다른 묶음이다. 한편 유효한 쌍의 뒤쪽 위치에 도달하면 앞쪽 무게는 이미 저장되어 있다. 이 두 사실로 잘못된 쌍을 반환하지 않으며, 답이 있는데 놓치지도 않음을 설명할 수 있다.

이 함수는 앞쪽 위치 중 같은 무게가 여러 번 나오면 최초 위치를 남긴다. 가능한 모든 쌍 중 특정 순서로 가장 작은 쌍을 고른다고 보장하지는 않는다. 문제에서 답 하나만 요구한다는 조건에 맞춘 선택이다. 평균 시간은 O(n), 추가 공간은 O(n)이다. 위치가 필요 없고 존재 여부만 묻는다면 딕셔너리 대신 집합을 쓸 수도 있다.

두 수의 합 유형에서 핵심은 두 반복문을 단순히 하나로 줄이는 데 있지 않다. 현재 값에 대해 필요한 과거 정보를 식으로 정하고, 그 정보만 저장하는 데 있다. 다음 문제에서도 “현재 값에서 무엇을 빼야 하는가”를 먼저 계산한다. 다만 과거 값 하나를 찾는 것에서 과거 값이 나타난 횟수를 세는 것으로 질문이 달라진다.

누적 합의 차이를 빈도표로 세기

구간을 두 경계의 차이로 표현한다

누적 합(prefix sum) P[r]을 처음 r개 기록의 합으로 정의한다. 아무 기록도 더하지 않은 P[0]은 0이다. 그러면 시작 위치 l부터 끝 경계 r 직전까지의 구간 합은 P[r] - P[l]이다. 두 누적 합에 공통으로 들어 있는 앞부분이 빠지고, 원하는 구간만 남기 때문이다.

구간은 [l, r)로 적는다. l은 포함하고 r은 포함하지 않는다는 뜻이다. 비어 있지 않은 구간만 세므로 l < r이어야 한다. 구간 합이 K라는 조건을 정리하면 P[l] = P[r] - K가 된다. 오른쪽 경계 r을 정한 순간, 찾아야 할 왼쪽 누적 합의 값이 하나로 정해진다.

예시에서 다섯 개 기록을 처리한 누적 합은 4다. K가 3이면 과거 누적 합 1을 찾는다. 누적 합 1은 두 개 기록 뒤와 네 개 기록 뒤에 한 번씩 나타났다. 따라서 다섯 번째 기록에서 끝나는 구간은 두 개다. 위치로 쓰면 [2, 5)와 [4, 5)이며, 각각 [2, -2, 3]과 [3]이다.

여기서 집합은 부족하다. 누적 합 1이 있었다는 사실만 저장하면 두 구간을 한 구간으로 세게 된다. 필요한 정보는 각 누적 합이 과거 경계에서 나타난 횟수다. 같은 값이라도 경계가 다르면 다른 시작점이므로 빈도를 모두 보존해야 한다.

조회하고 나서 현재 누적 합을 등록한다

처음 빈도표를 {0: 1}로 둔다. 이는 합이 0인 가상 기록을 추가한다는 뜻이 아니라, 첫 기록 앞에 있는 경계 P[0]을 한 번 저장한다는 뜻이다. 이 경계가 있어야 처음부터 시작하는 구간도 같은 조회식으로 셀 수 있다.

예시 기록에서 각 끝 경계가 추가하는 구간 수를 누적한다

끝 경계 r	현재 P[r]	P[r] - 3의 과거 횟수	누적 답
1	2	-1: 0회	0
2	1	-2: 0회	0
3	3	0: 1회	1
4	1	-2: 0회	1
5	4	1: 2회	3
6	3	0: 1회	4

각 행은 현재 누적 합을 빈도표에 넣기 전에 조회한 결과다. 마지막 답은 4이며, 구간은 [0, 3), [2, 5), [4, 5), [0, 6)이다. 처리한 기록이 늘어도 전체 누적 합 배열을 보관할 필요는 없다. 현재 합 하나와 과거 합들의 빈도표만 유지하면 된다.

정확성은 다음 불변식으로 설명할 수 있다. 끝 경계 r의 조회 직전, 빈도표는 P[0]부터 P[r-1]까지의 등장 횟수를 담고 있다. 따라서 P[r] - K의 빈도는 현재 경계에서 끝나는 유효한 시작점의 수와 같다. 그 수를 답에 더한 뒤 P[r]을 등록하면 다음 경계에서도 불변식이 유지된다.

각 구간은 오른쪽 경계가 하나이므로 서로 다른 반복에서 중복 계산되지 않는다. 모든 오른쪽 경계를 처리하므로 빠지는 구간도 없다. 음수나 0이 있어도 누적 합의 차이라는 등식은 그대로 성립한다. 값이 증가하는지 감소하는지를 가정하지 않는다는 점이 이 풀이의 적용 범위를 넓힌다.

n개 기록을 한 번 순회하고 매번 일정한 수의 해시 연산을 수행하므로 평균 시간은 O(n)이다. 서로 다른 누적 합은 최대 n+1개이므로 추가 공간은 O(n)이다. 충돌 때문에 연산 비용이 커지는 최악의 경우에는 전체 시간이 O(n²)까지 늘어날 수 있다. 이에 비해 느린 풀이는 해시 연산 없이 항상 O(n²) 시간과 O(1) 추가 공간으로 구간을 확인한다.

완성 코드

다음 내용을 main.py로 저장한다. 예시 입력은 문자열로 넣고, io.StringIO를 사용해 코딩 테스트의 줄 단위 입력을 흉내 낸다. 첫 줄은 기록 수와 목표 합, 둘째 줄은 기록이다. 실제 표준 입력을 기다리는 부분은 없다.

검증에서는 길이 0부터 6까지, 각 원소가 -2부터 2까지인 모든 배열을 만든다. 각 배열에 목표 합 -3부터 3까지를 적용해 두 풀이를 비교한다. 난수를 사용하지 않으므로 실행할 때마다 같은 순서로 같은 경우를 검사한다.

import io
from itertools import product


def count_slow(values, target):
    answer = 0
    for left in range(len(values)):
        total = 0
        for right in range(left, len(values)):
            total += values[right]
            if total == target:
                answer += 1
    return answer


def count_fast(values, target):
    frequency = {0: 1}
    prefix = 0
    answer = 0
    for value in values:
        prefix += value
        answer += frequency.get(prefix - target, 0)
        frequency[prefix] = frequency.get(prefix, 0) + 1
    return answer


def verify_all():
    checked = 0
    for length in range(7):
        for values in product(range(-2, 3), repeat=length):
            for target in range(-3, 4):
                slow = count_slow(values, target)
                fast = count_fast(values, target)
                if slow != fast:
                    raise AssertionError(
                        f"불일치: values={values}, target={target}, "
                        f"slow={slow}, fast={fast}"
                    )
                checked += 1
    return checked


def main():
    sample = "6 3\n2 -1 2 -2 3 -1\n"
    stream = io.StringIO(sample)
    n, target = map(int, stream.readline().split())
    values = list(map(int, stream.readline().split()))
    if len(values) != n:
        raise ValueError("기록 수가 입력과 다르다.")

    slow = count_slow(values, target)
    fast = count_fast(values, target)
    if slow != fast:
        raise AssertionError("예시 결과가 일치하지 않는다.")

    print(f"기록: {values}")
    print(f"목표 합: {target}")
    print(f"완전 탐색: {slow}")
    print(f"누적 합 + 해시: {fast}")

    checked = verify_all()
    print(f"전수 대조: {checked}개 통과")


if __name__ == "__main__":
    main()

줄별 해설

import io는 문자열을 입력 스트림처럼 읽기 위해 필요하다. product는 가능한 원소 조합을 순서대로 만든다. 두 모듈 모두 표준 라이브러리이므로 별도 설치가 필요 없다.

count_slow의 바깥 반복문은 시작점 left를 정한다. 그때마다 total을 0으로 되돌린다. 안쪽 반복문은 끝 위치를 하나씩 늘리며 새 원소만 더한다. 반복마다 구간을 잘라 sum을 다시 호출하지 않으므로, 시작점 하나당 O(n), 전체 O(n²)에 머문다.

if total == target은 현재 구간 하나의 조건만 판단한다. 합을 찾았다고 반복을 끝내지 않는다. 같은 시작점에서 더 긴 구간이 다시 목표 합을 만들 수 있기 때문이다. 특히 음수나 0이 포함되면 그러한 경우가 쉽게 생긴다.

count_fast의 frequency = {0: 1}은 시작 경계를 등록한다. prefix는 지금까지의 합이고, answer는 이미 처리한 오른쪽 경계들에서 찾은 구간 수다. 세 변수는 각각 과거의 빈도, 현재 위치의 상태, 누적 결과를 맡는다.

prefix += value 뒤에는 현재 기록까지 포함한 합이 준비된다. 이어지는 frequency.get(prefix - target, 0)은 필요한 왼쪽 경계의 수를 읽는다. 해당 값이 없으면 새 구간도 없으므로 0을 더한다. 마지막 갱신 줄은 같은 누적 합이 이전에도 나왔는지를 따져 횟수를 1 늘린다.

verify_all에서 range(7)은 길이 0을 포함해 6까지 검사한다. 빈 배열에서는 비어 있지 않은 구간이 없으므로 어떤 목표에도 답이 0이어야 한다. product는 길이가 0일 때도 빈 튜플 하나를 생성하므로 이 경계 조건을 별도로 작성하지 않아도 확인한다.

repeat=length는 정해진 길이의 모든 배열을 만든다. 원소 후보가 다섯 개이므로 길이가 하나 늘면 배열 수는 다섯 배가 된다. 전체 배열 수는 1 + 5 + 25 + 125 + 625 + 3125 + 15625 = 19531이고, 목표가 일곱 개이므로 비교 횟수는 136717이다.

두 결과가 다르면 그 입력과 두 답을 담은 예외를 발생시킨다. 단순히 실패 여부만 알리는 것보다 바로 반례를 재현하기 쉽다. assert 문 대신 명시적으로 예외를 발생시키므로, 파이썬의 최적화 실행 옵션에 따라 검증이 빠지지도 않는다.

main은 문자열에서 예시를 읽고 기록 수를 확인한다. 입력 형식의 모든 잘못을 검사하는 범용 입력기는 아니며, 준비한 예시를 실행하는 진입점이다. 끝의 조건문은 파일을 직접 실행할 때만 main을 호출한다. 다른 파일에서 함수를 가져오더라도 예시와 전수 대조가 자동 실행되지 않는다.

전수 대조는 정해진 작은 범위를 빠짐없이 확인한다는 뜻이다. 모든 크기의 입력에 대한 증명을 대신하지는 않는다. 불변식으로 풀이가 성립하는 이유를 설명하고, 전수 대조로 초기값 누락이나 갱신 순서 같은 구현 실수를 찾아내는 두 역할을 함께 사용한다.

실행 결과

macOS 또는 Linux에서 Python 3.12 이상으로 다음 명령을 실행한다. 컴파일 검사 명령은 문제가 없으면 아무것도 출력하지 않는다. 프로그램은 전수 대조를 마친 뒤 종료한다.

python3 -W error -m py_compile main.py
python3 main.py

프로그램의 예상 출력은 다음과 같다.

기록: [2, -1, 2, -2, 3, -1]
목표 합: 3
완전 탐색: 4
누적 합 + 해시: 4
전수 대조: 136717개 통과

빠른 풀이의 O(n)은 한 배열에 대한 처리 비용이다. 검증 프로그램 전체가 선형 시간이라는 뜻은 아니다. 전수 대조는 길이에 따라 경우의 수가 빠르게 늘어나므로 작은 범위에만 적용한다. 큰 입력에서의 처리 시간과 작은 입력을 모두 검사하는 검증 비용은 구별해야 한다.

실무에서 자주 틀리는 것

현재 누적 합을 먼저 등록한다

다음 두 줄은 순서가 바뀌었다. 목표가 0이면 방금 등록한 현재 경계를 자기 자신의 시작점으로 사용해 길이 0인 구간을 하나 더 센다. 예를 들어 기록이 [0]일 때 올바른 답은 1인데 이 순서는 2를 만든다.

frequency[prefix] = frequency.get(prefix, 0) + 1
answer += frequency.get(prefix - target, 0)

현재 경계보다 앞선 경계만 조회하도록 다음 순서로 고친다. 두 수의 합에서도 조회 후 등록이라는 순서가 같은 원소의 재사용을 막았다.

answer += frequency.get(prefix - target, 0)
frequency[prefix] = frequency.get(prefix, 0) + 1

처음의 0을 누락한다

빈 딕셔너리로 시작하면 첫 기록부터 시작하는 구간을 놓친다. 기록이 [3], 목표가 3이면 필요한 과거 합은 0인데 조회할 경계가 없다.

frequency = {}
prefix = 0
answer = 0

기록 앞의 경계를 한 번 등록한다. 이 초기값은 목표 합이 0인 경우에도 동일하게 필요하다.

frequency = {0: 1}
prefix = 0
answer = 0

개수를 묻는데 집합을 쓴다

집합은 같은 누적 합이 여러 번 등장했다는 정보를 지운다. 다음 코드는 필요한 값이 있었는지만 보고 매번 1을 더하므로 여러 시작점이 만드는 구간을 놓친다.

seen = {0}
prefix = 0
answer = 0
for value in values:
    prefix += value
    if prefix - target in seen:
        answer += 1
    seen.add(prefix)

존재 여부 대신 빈도를 저장한다. 기록 [0, 0], 목표 0에서는 오른쪽 경계마다 각각 1개와 2개를 더해 총 3개를 세어야 한다.

frequency = {0: 1}
prefix = 0
answer = 0
for value in values:
    prefix += value
    answer += frequency.get(prefix - target, 0)
    frequency[prefix] = frequency.get(prefix, 0) + 1

음수가 있는데 합이 커졌다고 탐색을 끝낸다

다음은 느린 정답을 만들 때도 나타나는 오류다. 양수만 있다는 조건 없이 합이 목표를 넘으면 중단하도록 작성했다.

for right in range(left, len(values)):
    total += values[right]
    if total == target:
        answer += 1
    if total > target:
        break

기록 [5, -2], 목표 3에서는 첫 값 뒤에 중단하여 전체 구간을 놓친다. 이 장의 입력 조건에서는 모든 끝 위치를 확인해야 한다.

for right in range(left, len(values)):
    total += values[right]
    if total == target:
        answer += 1

한눈에 보기

질문에 따라 저장할 정보와 자료구조를 선택한다

질문	저장할 정보	도구	평균 비용
본 적이 있는가	등장한 값	set	조회 O(1)
몇 번 나왔는가	값별 횟수	dict, Counter	조회·갱신 O(1)
합을 이루는 두 위치가 있는가	이전 값의 위치	dict	전체 O(n)
합이 K인 연속 구간은 몇 개인가	이전 누적 합의 횟수	누적 합과 dict	전체 O(n)
구간 합을 직접 모두 확인하는가	현재 구간 합	중첩 반복문	전체 O(n²)

해시를 쓰기로 정하기 전에, 같은 값의 여러 등장을 하나로 합쳐도 되는지 판단한다. 존재만 물으면 집합이 맞고, 개수를 물으면 빈도가 필요하다. 위치를 출력해야 하면 위치를 저장해야 한다. 도구의 이름보다 답을 복원하는 데 필요한 정보가 먼저다.

구간 문제에서는 경계를 기준으로 식을 세우면 저장할 정보가 드러난다. 이번 문제의 식은 P[l] = P[r] - K이고, 그 결과 과거 누적 합의 빈도가 필요해졌다. 다음 장에서 구간을 옮기며 처리하는 방법을 살펴볼 때도, 값을 버려도 되는 조건이 있는지 먼저 확인해야 한다.

연습 문제

1. 택배 표식이 ["별", "달", "별", "숲", "달", "달"]로 주어진다. 두 번 이상 등장한 표식만 문자열 정렬 순서로 출력하는 코드를 작성하라. 빈도표를 만든 뒤 무엇을 검사해야 하는지 설명하라.
2. 포장 무게가 [7, 3, 7, 5], 목표 합이 14일 때 find_pair의 반환값을 구하라. 무게가 [7] 하나뿐인 경우의 결과도 쓰고, 현재 무게를 먼저 등록하면 어떤 문제가 생기는지 설명하라.
3. 재고 기록이 [1, -1, 0], 목표 합이 0이다. 각 오른쪽 경계에서 추가되는 구간 수와 최종 답을 손으로 구하라. 빈도표에 같은 누적 합이 여러 번 기록되는 이유도 설명하라.
4. 합이 K인 구간의 개수 대신 가장 긴 구간의 길이를 구하려 한다. 답이 없으면 0을 반환한다. 누적 합마다 어떤 위치를 저장해야 하는지 정하고 함수를 작성하라. 기록 [2, -2, 3, 0, -3], 목표 0으로 확인하라.

정답과 해설

1. 두 번 이상 나온 표식

빈도가 2 이상인지 검사한다. 집합만 만들면 한 번 나온 표식과 여러 번 나온 표식을 구별할 수 없다. 결과 목록을 정렬해 출력 순서를 명시한다.

from collections import Counter

labels = ["별", "달", "별", "숲", "달", "달"]
counts = Counter(labels)
result = sorted(label for label, count in counts.items() if count >= 2)
print(result)

출력은 ['달', '별']이다. 표식 수가 n개, 서로 다른 표식이 u개라면 빈도를 세는 평균 시간은 O(n), 정렬까지 포함한 시간은 O(n + u log u), 추가 공간은 O(u)다. 정렬 대상이 일부 표식뿐이어도 이 식은 상한으로 쓸 수 있다.

2. 서로 다른 두 묶음

반환값은 (0, 2)다. 첫 번째 7은 조회 때 상대가 없으므로 저장된다. 세 번째 무게 7을 처리하면 앞서 저장된 7을 찾아 두 위치를 반환한다. [7]만 주어지면 답은 None이다.

먼저 등록하면 첫 무게 7을 저장한 직후 필요한 7을 찾게 되어 (0, 0)을 반환할 수 있다. 서로 다른 위치라는 조건을 어긴다. 따라서 조회 시점에 저장된 위치가 모두 현재 위치보다 앞선다는 불변식을 유지해야 한다.

3. 같은 누적 합이 만드는 여러 구간

누적 합은 시작 경계부터 [0, 1, 0, 0]이다. 첫 경계에서는 과거 합 1이 없으므로 0개를 더한다. 두 번째 경계에서는 과거 합 0이 한 번이므로 1개, 세 번째 경계에서는 과거 합 0이 두 번이므로 2개를 더한다. 최종 답은 3이다.

구간은 [0, 2), [0, 3), [2, 3)이다. 누적 합이 같더라도 경계 위치가 다르면 시작점이 다르다. 같은 값을 합쳐 저장하되, 그 값이 대표하는 경계 수는 빈도로 남겨야 한다.

4. 가장 긴 구간에는 최초 위치가 필요하다

현재 오른쪽 경계가 r일 때 길이는 r - l이다. 같은 누적 합에 대응하는 l이 여러 개라면 가장 작은 l이 가장 긴 구간을 만든다. 그러므로 누적 합마다 최초 경계만 저장한다. 시작 경계 0도 처음부터 등록한다.

def longest_segment(values, target):
    first = {0: 0}
    prefix = 0
    longest = 0

    for right, value in enumerate(values, start=1):
        prefix += value
        need = prefix - target
        if need in first:
            longest = max(longest, right - first[need])
        if prefix not in first:
            first[prefix] = right

    return longest


print(longest_segment([2, -2, 3, 0, -3], 0))

출력은 5다. 전체 기록의 합이 0이므로 길이 5인 구간이 답이다. 조회 직전 최초 위치표가 이전 경계들의 가장 이른 위치를 담고 있다는 불변식으로 정확성을 설명할 수 있다. 평균 시간은 O(n), 추가 공간은 O(n)이다.

이 함수도 작은 입력으로 대조할 수 있다. 완성 코드의 느린 풀이에서 조건이 맞을 때 횟수를 늘리는 줄을 longest = max(longest, right - left + 1)로 바꾸고, 초기값과 반환값도 longest로 바꾼다. 같은 배열과 목표 범위를 전수 검사하면, 개수 문제의 빈도표를 길이 문제의 최초 위치표로 바꾸는 과정에서 생긴 실수를 확인할 수 있다.