패턴 구현

이 장에서는 면접에서 가장 자주 쓰는 세 패턴인 투 포인터, 해시 맵, 슬라이딩 윈도우를 Python으로 구현합니다. 그중 핵심인 슬라이딩 윈도우는 한 줄씩 설명한 뒤 C++, Java, TypeScript로도 옮겨, 언어가 바뀌어도 같은 생각이 어떻게 이어지는지 보여 줍니다.

투 포인터: 정렬된 배열의 중복 제거

같은 방향으로 움직이는 두 포인터입니다. read는 모든 원소를 읽고, write는 다음에 남길 값을 쓸 자리를 가리킵니다. 추가 배열 없이 제자리에서 정리하므로 공간은 O(1)입니다.

def dedupe_sorted(nums: list[int]) -> int:
    """정렬된 nums에서 중복을 제자리에서 지우고 남은 개수를 돌려준다."""
    write = 0
    for read in range(len(nums)):
        if read == 0 or nums[read] != nums[read - 1]:
            nums[write] = nums[read]
            write += 1
    return write


data = [1, 1, 2, 3, 3, 3, 5]
count = dedupe_sorted(data)
print(count, data[:count])  # 4 [1, 2, 3, 5]

해시 맵: 합이 target인 두 원소의 위치

정렬되지 않은 배열에서 합이 target인 두 원소의 인덱스를 찾습니다. 지금 값 x에 대해 필요한 짝은 target - x이므로, 지금까지 본 값의 위치를 딕셔너리에 저장해 두면 한 번 훑는 동안 답을 찾을 수 있습니다. 정렬하면 원래 인덱스를 잃기 때문에 이 문제에서는 투 포인터보다 해시 맵이 알맞습니다.

def pair_indices(nums: list[int], target: int) -> tuple[int, int] | None:
    index_of: dict[int, int] = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in index_of:
            return index_of[need], i
        index_of[x] = i  # 짝을 확인한 뒤에 넣어야 자기 자신과 짝이 되지 않는다
    return None


print(pair_indices([8, 3, 5, 11, 2], 13))  # (0, 2)
print(pair_indices([1, 2], 10))            # None

슬라이딩 윈도우: 중복 없는 가장 긴 구간

문자열에서 같은 문자가 두 번 나오지 않는 가장 긴 연속 구간의 길이를 구합니다. 창 [left, right] 안에는 중복 문자가 없다는 불변식을 유지하면서 right를 한 칸씩 늘립니다.

def longest_unique_window(s: str) -> int:
    last_seen: dict[str, int] = {}   # 문자 -> 마지막으로 본 위치
    left = best = 0
    for right, ch in enumerate(s):
        if last_seen.get(ch, -1) >= left:
            left = last_seen[ch] + 1  # 창 안의 중복을 건너뛴다
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best


for text in ["tastedev", "aaaa", "interview", ""]:
    print(repr(text), longest_unique_window(text))
# 'tastedev' 5 / 'aaaa' 1 / 'interview' 6 / '' 0

한 줄씩 보면 다음과 같습니다.

• last_seen은 각 문자를 마지막으로 본 위치를 기억합니다. 문자를 지우는 대신 위치를 기억하므로 왼쪽 끝을 한 번에 건너뛸 수 있습니다.
• last_seen.get(ch, -1) >= left는 "이 문자가 지금 창 안에 이미 있는가"를 뜻합니다. 창 왼쪽 바깥에서 본 위치는 무시해야 하므로 left와 비교하는 부분이 중요합니다.
• 중복이 있으면 left를 그 문자의 직전 위치 바로 다음으로 옮깁니다. left는 앞으로만 움직이므로 전체 이동은 n번을 넘지 않습니다.
• 위치를 갱신한 뒤 현재 창 길이 right - left + 1로 최댓값을 갱신합니다.

전체 시간은 O(n)이고, 공간은 서로 다른 문자 수 σ에 대해 O(min(n, σ))입니다. 면접에서는 left와 비교하는 조건을 빠뜨려 "abba" 같은 입력에서 왼쪽 끝이 뒤로 가는 버그가 자주 나옵니다. 이 입력의 답은 2입니다.

C++

std::unordered_map으로 마지막 위치를 저장합니다. 문자열 길이는 size_t이므로 인덱스를 int로 바꿀 때 형 변환을 분명히 합니다.

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>

int longestUniqueWindow(const std::string& s) {
    std::unordered_map<char, int> lastSeen;
    int left = 0, best = 0;
    for (int right = 0; right < static_cast<int>(s.size()); ++right) {
        auto it = lastSeen.find(s[right]);
        if (it != lastSeen.end() && it->second >= left) {
            left = it->second + 1;
        }
        lastSeen[s[right]] = right;
        best = std::max(best, right - left + 1);
    }
    return best;
}

int main() {
    std::cout << longestUniqueWindow("tastedev") << '\n';  // 5
    std::cout << longestUniqueWindow("abba") << '\n';      // 2
}

Java

HashMap<Character, Integer>를 씁니다. get이 null을 돌려줄 수 있으므로 Integer로 받아 확인합니다.

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueWindow {
    static int longestUniqueWindow(String s) {
        Map<Character, Integer> lastSeen = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            Integer prev = lastSeen.get(ch);
            if (prev != null && prev >= left) {
                left = prev + 1;
            }
            lastSeen.put(ch, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longestUniqueWindow("tastedev")); // 5
        System.out.println(longestUniqueWindow("abba"));     // 2
    }
}

TypeScript

Map<string, number>를 씁니다. Array.from(s)로 나누면 이모지처럼 두 코드 단위로 된 문자도 한 글자로 다룹니다.

function longestUniqueWindow(s: string): number {
  const lastSeen = new Map<string, number>();
  const chars = Array.from(s);
  let left = 0;
  let best = 0;
  for (let right = 0; right < chars.length; right++) {
    const prev = lastSeen.get(chars[right]);
    if (prev !== undefined && prev >= left) left = prev + 1;
    lastSeen.set(chars[right], right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

console.log(longestUniqueWindow("tastedev")); // 5
console.log(longestUniqueWindow("abba")); // 2

C++의 char와 Java의 charAt은 바이트나 UTF-16 코드 단위 기준이므로, 한글이나 이모지가 섞인 입력을 다룰 때는 이 점을 면접관에게 짚어 두면 좋습니다. 대부분의 면접 문제는 영문 소문자나 ASCII로 입력을 제한하므로, 그럴 때는 크기 26 또는 128인 배열로 해시 맵을 대신해 상수 배를 줄일 수도 있습니다.

정리

투 포인터는 정렬이나 제자리 정리에, 해시 맵은 "이미 본 값"을 빠르게 찾을 때, 슬라이딩 윈도우는 연속 구간의 최적값을 구할 때 씁니다. 세 패턴 모두 핵심은 반복문이 도는 동안 지켜야 할 불변식을 정하고, 포인터가 앞으로만 움직이게 만드는 것입니다. 언어를 바꿔도 이 뼈대는 그대로이며, 달라지는 것은 해시 맵 API와 문자 단위 정도입니다.