패턴 연습 문제

이 장의 문제는 패턴을 손에 익히기 위해 새로 만든 연습 문제입니다. 각 문제마다 먼저 스스로 앞 장의 절차대로 질문 · 예시 · 무차별 대입 · 최적화를 거친 뒤 풀이를 확인하세요. 풀이를 본 뒤에는 코드를 가리고 다시 써 보는 것이 가장 효과적입니다.

문제 1: 합이 정확히 k인 구간 개수 (누적 합 + 해시 맵)

하루 단위 수입과 지출이 정수 배열 amounts로 주어집니다(음수 포함). 연속된 날들의 합이 정확히 k가 되는 구간의 개수를 구하세요.

예: amounts = [1, 2, -1, 2, 1], k = 3이면 [1, 2], [2, -1, 2], [2, 1]로 답은 3입니다.

접근: 음수가 있으므로 슬라이딩 윈도우가 통하지 않습니다. 앞에서부터의 누적 합을 p라 하면, 구간 합이 k인 것은 p[j] - p[i] = k, 즉 지금 누적 합에서 k를 뺀 값이 이전에 몇 번 나왔는지와 같습니다. 누적 합의 등장 횟수를 해시 맵에 세면 됩니다. 빈 접두사를 나타내는 0을 처음에 한 번 넣어 두는 것이 핵심입니다.

from collections import defaultdict


def count_sum_k(amounts: list[int], k: int) -> int:
    seen = defaultdict(int)
    seen[0] = 1           # 아무것도 더하지 않은 상태
    prefix = count = 0
    for x in amounts:
        prefix += x
        count += seen[prefix - k]
        seen[prefix] += 1
    return count


print(count_sum_k([1, 2, -1, 2, 1], 3))  # 3
print(count_sum_k([0, 0], 0))            # 3

복잡도: 시간 O(n), 공간 O(n).

문제 2: 합이 target 이하인 쌍의 개수 (투 포인터)

오름차순으로 정렬된 정수 배열 nums가 있습니다. i < j이고 nums[i] + nums[j] <= target인 쌍의 개수를 구하세요.

예: nums = [1, 2, 3, 4, 6], target = 6이면 (1, 2), (1, 3), (1, 4), (2, 3), (2, 4)로 답은 5입니다.

접근: 양 끝에 포인터를 둡니다. nums[lo] + nums[hi] <= target이면 lo와 짝지을 수 있는 원소가 lo + 1부터 hi까지 모두이므로 hi - lo개를 한꺼번에 세고 lo를 늘립니다. 그렇지 않으면 hi를 줄입니다.

def count_pairs_at_most(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    count = 0
    while lo < hi:
        if nums[lo] + nums[hi] <= target:
            count += hi - lo
            lo += 1
        else:
            hi -= 1
    return count


print(count_pairs_at_most([1, 2, 3, 4, 6], 6))  # 5
print(count_pairs_at_most([5, 5, 5], 9))        # 0

복잡도: 시간 O(n)(정렬되지 않았다면 정렬 포함 O(n log n)), 공간 O(1).

문제 3: 서로 다른 값이 k개 이하인 가장 긴 구간 (슬라이딩 윈도우 + 해시 맵)

접속 기록이 사용자 ID 배열 log로 주어집니다. 서로 다른 ID가 최대 k개만 들어 있는 가장 긴 연속 구간의 길이를 구하세요.

예: log = ["a", "b", "a", "c", "c", "c"], k = 2이면 ["a", "c", "c", "c"]의 길이 4가 답입니다.

접근: 창 안의 ID별 개수를 해시 맵에 둡니다. 오른쪽에서 하나를 넣은 뒤 서로 다른 ID가 k개를 넘으면, 넘지 않을 때까지 왼쪽에서 빼고 개수가 0이 된 ID는 맵에서 지웁니다. 맵의 크기가 곧 서로 다른 ID의 수입니다.

from collections import Counter


def longest_at_most_k_distinct(log: list[str], k: int) -> int:
    counts: Counter[str] = Counter()
    left = best = 0
    for right, user in enumerate(log):
        counts[user] += 1
        while len(counts) > k:
            counts[log[left]] -= 1
            if counts[log[left]] == 0:
                del counts[log[left]]
            left += 1
        best = max(best, right - left + 1)
    return best


print(longest_at_most_k_distinct(["a", "b", "a", "c", "c", "c"], 2))  # 4
print(longest_at_most_k_distinct(["x", "y"], 0))                      # 0

복잡도: 시간 O(n), 공간 O(k).

문제 4: 딱 한 번 나온 첫 ID (해시 맵으로 개수 세기)

이벤트 ID 배열에서 전체에 정확히 한 번만 나온 ID 가운데 가장 먼저 나온 것을 찾으세요. 없으면 None을 돌려줍니다.

예: ["k", "m", "k", "p", "m"]이면 답은 "p"입니다.

접근: 첫 번째 훑기에서 개수를 세고, 두 번째 훑기에서 원래 순서대로 개수가 1인 첫 값을 찾습니다. 두 번 훑어도 시간은 O(n)입니다.

from collections import Counter


def first_unique(events: list[str]) -> str | None:
    counts = Counter(events)
    for event in events:
        if counts[event] == 1:
            return event
    return None


print(first_unique(["k", "m", "k", "p", "m"]))  # p
print(first_unique(["k", "k"]))                 # None

문제 5: 정렬된 배열에서 값의 등장 횟수 (이분 탐색)

정렬된 배열 nums에서 값 x가 몇 번 나오는지 O(log n)에 구하세요.

접근: x 이상인 첫 위치와 x보다 큰 첫 위치의 차이가 등장 횟수입니다. 표준 라이브러리 bisect가 두 위치를 바로 알려 줍니다. 면접에서 직접 구현을 요구하면 아래처럼 lower_bound를 써 보입니다.

from bisect import bisect_left, bisect_right


def lower_bound(nums: list[int], x: int) -> int:
    lo, hi = 0, len(nums)            # 답은 [lo, hi] 안에 있다
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


nums = [1, 2, 2, 2, 5, 7]
print(bisect_right(nums, 2) - bisect_left(nums, 2))  # 3
print(lower_bound(nums, 2), lower_bound(nums, 6))    # 1 5

정리

다섯 문제는 각각 누적 합, 투 포인터, 가변 슬라이딩 윈도우, 개수 세기, 이분 탐색을 연습합니다. 풀이를 외우기보다 "음수가 있으니 윈도우가 안 된다", "정렬되어 있으니 양 끝에서 좁힌다"처럼 패턴을 고른 이유를 말로 설명할 수 있는지 확인하세요. 같은 문제를 다른 언어로 다시 풀어 보는 것도 좋은 복습이 됩니다.