Introduction
이번 레슨에서는 정수 배열에서 중복 값이 없는 가장 긴 연속 구간의 길이를 구합니다. 배열의 일부를 선택하되, 선택한 구간 안에는 같은 값이 두 번 등장하면 안 됩니다.
슬라이딩 윈도우는 배열 전체를 대상으로 같은 계산을 반복하는 대신, 현재 살펴보는 구간의 시작과 끝을 이동하면서 필요한 상태를 갱신하는 방법입니다. 구현에서는 두 경계를 움직이는 코드보다 각 경계가 무엇을 포함하는지 정의하는 일이 먼저입니다.
왼쪽 경계가 현재 원소를 포함하는지, 오른쪽 경계가 다음에 읽을 위치인지, 이전에 본 값이 아직 구간 안에 있는지를 구분해야 합니다. 이 정의가 일관되면 길이 계산과 중복 처리를 같은 규칙으로 설명할 수 있습니다.
문제를 정의한 다음, 틀린 접근을 반례로 살펴보겠습니다. 이어서 복잡도를 계산하고, 실행 환경과 상태 관리에서 생기는 함정을 확인한 뒤 모범답안을 작성하겠습니다. 코드는 JavaScript를 사용하며, 특정 플랫폼의 입출력 형식에 의존하지 않는 함수로 구현합니다.
문제
중복 값이 없는 가장 긴 연속 구간
정수 배열 items가 주어집니다. 같은 값이 두 번 이상 등장하지 않는 연속 구간 중 가장 긴 구간의 길이를 반환하세요.
이번 레슨의 입력 조건은 다음과 같습니다.
배열의 길이 n은 0 이상 20만 이하입니다.
각 원소는 음수 10억 이상 양수 10억 이하의 정수입니다.
선택하는 원소들은 원래 배열에서 연속해야 합니다.
입력 배열의 순서와 값을 변경하지 않습니다.
빈 배열의 답은 0입니다.
가장 긴 구간이 여러 개라면 길이만 반환합니다.
다음 입력을 보겠습니다.
[1, 2, 3, 1, 2, 3, 2, 2]
앞의 [1, 2, 3]은 중복이 없는 연속 구간이고 길이는 3입니다. 이 입력에는 길이가 4 이상인 중복 없는 연속 구간이 없으므로 답은 3입니다.
다음 입력은 답이 1입니다.
[7, 7, 7]
서로 다른 값이 하나뿐이라는 이유로 0을 반환하면 안 됩니다. 원소 하나를 선택한 구간은 중복이 없으므로 유효합니다.
연속 구간과 부분 수열을 구분합니다
다음 배열에서 값이 서로 다른 원소만 고르면 [1, 2, 3]을 만들 수 있습니다.
[1, 2, 2, 3]
하지만 그 선택은 가운데 원소 하나를 건너뜁니다. 이 문제에서 허용하는 연속 구간이 아닙니다.
실제 답은 2입니다. [1, 2] 또는 [2, 3]을 선택할 수 있습니다. 배열 전체에서 서로 다른 값의 개수를 세는 코드로는 연속 구간의 길이를 구할 수 없습니다.
구간을 반열린 구간으로 정의합니다
시작 위치는 포함하고 끝 위치는 포함하지 않는 구간을 반열린 구간이라고 부릅니다. 이번 레슨에서는 현재 구간을 [left, right)로 표현하겠습니다.
left
현재 구간에 포함되는 가장 왼쪽 인덱스
right
현재 구간에 아직 포함되지 않은 다음 인덱스
best
지금까지 확인한 유효한 구간의 최대 길이
예를 들어 [1, 4)는 인덱스 1, 2, 3을 포함합니다. 길이는 4 - 1이므로 3입니다.
[0, 0)은 빈 구간이고 길이는 0입니다. 배열 전체를 선택하면 [0, n)이며 길이는 n입니다. 끝 위치로 n을 사용할 수 있지만, items[n]을 읽어도 된다는 뜻은 아닙니다.
이번 구현에서는 반복문을 시작할 때 [left, right)에 중복이 없도록 유지합니다. 다음에 처리할 값은 items[right]입니다. 필요한 만큼 왼쪽 경계를 조정하고 그 값을 포함한 뒤, right를 하나 증가시키겠습니다.
길이는 항상 right - left로 계산합니다. 양쪽 끝을 모두 포함하는 구간에서 사용하는 right - left + 1을 이 구현에 섞으면 한 칸을 더 세게 됩니다.
오른쪽 원소를 추가했을 때 무엇을 유지해야 할까요
현재 구간이 [1, 2, 3]이고 다음 값이 4라면 그대로 확장할 수 있습니다.
다음 값이 2라면 기존의 2와 새로 들어오는 2가 중복됩니다. 기존의 2를 제외할 때까지 왼쪽 경계를 이동해야 합니다. 앞의 1만 제외하면 [2, 3, 2]가 되어 여전히 중복이 남습니다.
기존의 2까지 제외하면 [3, 2]가 됩니다. 현재 원소로 끝나는 중복 없는 구간을 가능한 길게 유지하려면 여기에서 이동을 멈춰야 합니다. 3까지 제거하면 유효성은 유지되지만 길이를 불필요하게 줄이게 됩니다.
따라서 두 가지 조건을 함께 지키겠습니다. 현재 구간에 중복이 없어야 하고, 그 조건을 만족하는 범위에서 왼쪽 경계를 가장 왼쪽에 두어야 합니다.
틀린 접근
중복이 나오면 현재 구간을 전부 버립니다
현재까지 모은 값을 저장하다가 중복을 만나면 저장한 값을 모두 지우는 방법을 생각할 수 있습니다. 다음 입력에서 이 방법의 문제를 볼 수 있습니다.
[1, 2, 3, 2, 4, 5]
인덱스 3의 값 2를 만났을 때 앞에서 만든 [1, 2, 3]을 전부 버리면 새 구간은 [2]가 됩니다. 그 뒤의 4와 5를 추가해도 길이는 3입니다. 앞에서 확인한 최대 길이 역시 3이므로 이 방법은 3을 반환합니다.
하지만 정답 구간은 [3, 2, 4, 5]이고 길이는 4입니다. 중복을 해소하기 위해 제거해야 했던 원소는 앞의 1과 2입니다. 값 3까지 제거할 이유는 없었습니다.
중복이 생겼다는 사실은 현재 구간 전체가 앞으로 쓸모없다는 뜻이 아닙니다. 중복을 만든 이전 위치까지만 제외하면 나머지 연속 구간을 계속 사용할 수 있습니다.
중복이 나오면 왼쪽 원소를 한 번만 제거합니다
현재 구간의 값을 Set에 저장한다고 하겠습니다. Set은 어떤 값이 현재 구간에 있는지 확인하는 데 사용합니다.
다음 코드는 잘못된 처리의 일부입니다.
if (seen.has(value)) {
seen.delete(items[left])
left += 1
}seen.add(value)
중복을 한 번 발견했으니 왼쪽 원소도 한 번만 제거하면 된다고 생각하기 쉽습니다. 하지만 제거한 원소가 중복을 일으킨 값이라는 보장이 없습니다.
[1, 2, 3] 뒤에 2가 들어올 때 위 코드는 1만 제거합니다. 실제 구간은 [2, 3, 2]인데 Set에는 2와 3만 들어 있습니다. Set은 같은 값을 두 번 저장하지 않으므로, 자료구조만 보고 실제 구간의 중복을 알아낼 수도 없습니다.
여기에 4와 5가 추가되면 잘못된 코드는 [2, 3, 2, 4, 5]를 길이 5의 유효한 구간으로 계산할 수 있습니다. 실제 정답은 4입니다.
이 방식에서는 한 번 제거하는 if가 아니라, 새 값이 현재 구간에서 사라질 때까지 제거하는 while이 필요합니다. 유효한 구간을 유지하는 동안에는 각 값이 한 번만 있으므로, 왼쪽 원소 하나를 제거할 때 Set에서도 그 값을 제거해도 됩니다.
과거에 본 값이면 무조건 그 위치 다음으로 이동합니다
원소를 하나씩 제거하는 대신, 각 값이 마지막으로 등장한 위치를 기록하면 필요한 위치로 바로 이동할 수 있습니다.
여기에서 다음과 같은 코드를 작성하면 문제가 생깁니다.
const previous = lastSeen.get(value)if (previous !== undefined) {
left = previous + 1
}
반례는 [1, 2, 2, 1]입니다.
인덱스 2의 값 2를 처리하면 이전의 2가 있는 인덱스 1을 제외해야 합니다. 따라서 left는 2가 됩니다.
이후 인덱스 3의 값 1을 읽습니다. 값 1의 과거 위치는 0이지만, 현재 구간은 인덱스 2부터 시작하므로 과거의 1은 이미 구간 밖에 있습니다. 이 값 때문에 왼쪽 경계를 움직일 필요가 없습니다.
그런데 위 코드는 left를 0 + 1로 설정합니다. 왼쪽 경계가 2에서 1로 되돌아가면서 [2, 2, 1]을 다시 포함합니다. 중복이 있는 구간을 길이 3으로 계산하지만 실제 답은 2입니다.
마지막 등장 위치를 기록한 자료구조에는 현재 구간 밖의 정보도 남아 있습니다. 과거에 본 적이 있는지와 현재 구간 안에서 중복되는지는 서로 다른 조건입니다.
경계 위에 있는 중복을 제외합니다
이전 위치가 현재 구간 안에 있는지 확인할 때 다음 조건을 쓰는 경우가 있습니다.
previous > left하지만 왼쪽 경계는 구간에 포함됩니다. 이전 위치가 left와 같아도 현재 구간 안에 있는 중복입니다.
[7, 7]에서 새로 읽는 7의 이전 위치는 0이고 left도 0입니다. 위 조건은 거짓이므로 경계가 이동하지 않습니다. 결과적으로 같은 값 두 개를 모두 포함하고 길이 2를 반환하게 됩니다.
올바른 조건은 previous >= left입니다. 등호의 필요성은 암기할 사항이 아니라, 왼쪽 경계를 포함한다는 구간 정의에서 결정됩니다.
인덱스 0을 없는 값으로 취급합니다
다음 코드도 [7, 7]을 잘못 처리합니다.
if (previous && previous >= left) {
left = previous + 1
}JavaScript의 조건식에서 숫자 0은 거짓으로 평가됩니다. 하지만 인덱스 0은 유효한 위치입니다.
이 레슨에서는 Map에 0 이상의 인덱스만 저장합니다. 따라서 get의 결과가 undefined인지 확인하면 아직 등장하지 않은 값과 인덱스 0에 등장한 값을 구분할 수 있습니다.
유효성을 복구하기 전에 최대 길이를 갱신합니다
[1, 2] 뒤에 1이 들어왔을 때, 일단 새 원소까지 포함하면 길이는 3이 됩니다. 하지만 그 상태의 [1, 2, 1]은 유효한 후보가 아닙니다.
이 길이를 먼저 best에 저장하고 나중에 왼쪽 경계를 이동하면 잘못된 답이 남습니다. 이후에 구간을 올바르게 고쳐도 이미 기록한 최대값이 자동으로 줄어들지는 않습니다.
최대 길이는 중복을 제거하고 새 원소를 포함한 다음에 갱신해야 합니다. 답을 갱신하는 시점에는 현재 구간이 반드시 문제의 조건을 만족해야 합니다.
복잡도
모든 시작점에서 다시 탐색하면 얼마나 걸릴까요
가장 직접적인 풀이는 시작점을 하나 정하고 오른쪽으로 원소를 추가하는 방법입니다. 중복이 나오면 멈추고, 다음 시작점에서 다시 탐색합니다. 각 시작점에서는 새로운 Set을 사용한다고 하겠습니다.
모든 값이 서로 다르면 중간에 탐색을 멈출 수 없습니다. 시작점 0에서는 n개, 시작점 1에서는 n - 1개를 확인합니다. 원소를 확인하는 총횟수는 n × (n + 1) / 2입니다.
n이 20만이면 약 200억 번의 원소 확인이 필요합니다. 실제 실행 시간은 환경마다 다르지만, 같은 구간을 여러 번 확인하는 구조 자체를 개선해야 하는 규모입니다. 각 자료구조 연산을 평균 O(1)로 가정하면 이 풀이의 최악 시간 복잡도는 O(n²)입니다.
모든 시작점과 끝점을 고른 뒤, 그때마다 구간을 처음부터 읽어 중복을 검사하면 더 많은 작업이 생깁니다. O(n²)개의 구간마다 최대 O(n)의 검사가 필요하므로 최악 시간 복잡도는 O(n³)까지 증가합니다.
이 문제에서 줄여야 할 것은 중복 확인 자체가 아닙니다. 이미 확인한 원소를 시작점마다 반복해서 확인하는 작업입니다.
반복문이 두 개 있어도 O(n)일 수 있습니다
현재 구간을 Set으로 관리하는 풀이에서는 바깥 반복문이 오른쪽 경계를 움직이고, 안쪽 반복문이 왼쪽 경계를 움직입니다.
코드에 반복문이 두 개 있다는 이유만으로 O(n²)이라고 결론내릴 수는 없습니다. 안쪽 반복문이 바깥 반복마다 처음부터 다시 실행되는지 확인해야 합니다.
이 풀이에서 right는 처음부터 끝까지 총 n번 증가합니다. left도 뒤로 돌아가지 않으므로 전체 실행 동안 최대 n번 증가합니다. 어떤 순간에는 왼쪽 원소를 여러 개 제거하더라도, 같은 인덱스를 나중에 다시 제거하지는 않습니다.
여러 연산의 비용을 전체 실행에 걸쳐 합산해 보는 분석을 분할 상환 분석이라고 합니다. 여기에서는 각 원소가 한 번 들어오고 최대 한 번 나간다는 사실로 총 작업량을 계산합니다.
Set의 조회, 삽입, 삭제를 평균 O(1)로 가정하면 전체 시간은 평균 O(n)입니다. 특정 입력 하나가 아니라 전체 원소의 추가와 제거 횟수에 근거한 설명입니다.
마지막 등장 위치를 사용해도 같은 경계 원칙이 필요합니다
각 값의 마지막 위치를 저장하면 왼쪽 원소를 하나씩 제거하지 않고 필요한 위치로 바로 이동할 수 있습니다. 오른쪽 원소 하나를 처리할 때 조회와 갱신을 일정 횟수 수행합니다.
Map의 조회와 갱신을 평균 O(1)로 가정하면 전체 시간은 평균 O(n)입니다. 이 설명은 해시 기반 자료구조에 대한 평균 비용 가정을 포함합니다. 모든 구현과 모든 상황에서 개별 연산의 최악 비용이 O(1)이라고 주장하는 것은 아닙니다.
입력 전체에 등장하는 서로 다른 값의 수를 d라고 하겠습니다. 마지막 등장 위치를 지우지 않고 보관하는 구현은 추가 공간 O(d)를 사용합니다. d는 최대 n이므로 최악의 추가 공간은 O(n)입니다.
현재 구간의 값만 저장하는 Set 구현은 최대 구간 길이를 w라고 할 때 추가 공간 O(w)를 사용합니다. 두 구현 모두 전체 시간은 평균 O(n)이지만, 보관하는 정보의 범위는 다릅니다.
입력 배열이 이미 메모리에 있다는 전제에서 계산한 추가 공간입니다. 표준 입력 전체를 배열로 변환하는 프로그램이라면 입력 저장에 필요한 O(n) 공간도 전체 메모리 사용량에 포함해야 합니다.
모든 원소를 확인하는 작업은 남습니다
정답에 영향을 줄 수 있는 원소를 읽지 않고 건너뛸 수는 없습니다. 읽지 않은 위치의 값 하나가 바뀌면 가장 긴 유효 구간의 길이가 달라질 수 있기 때문입니다.
따라서 일반적인 입력에서 모든 원소를 확인하는 선형 작업은 필요합니다. 이번 문제에서는 평균 O(n) 풀이를 만든 뒤, 불필요한 복사와 상태 저장을 줄이는 쪽으로 구현을 개선하는 것이 적절합니다.
현장과 인터뷰에서 같은 경계 실수가 반복됩니다. 고정 길이 윈도우로 요청을 자를 때 끝 경계를 포함 여부로 잘못 두면, 같은 초 구간에 요청이 몰려 한 사용자만 제한에 걸리거나 반대로 제한이 비는 현상이 납니다. 경계 한 칸의 정의가 곧 트래픽 제어의 공정성이 됩니다.
시계열 점수를 시간 구간으로 자를 때도 비슷합니다. 학습에 쓰는 구간과 온라인에서 집계하는 구간의 열림과 닫힘이 어긋나면, 같은 이벤트가 한쪽에는 들어가고 다른 쪽에는 빠집니다. 모델과 운영 지표가 어긋날 때 먼저 확인할 것은 윈도우 경계의 포함 규칙입니다.
시스템 함정
경계 이동이 O(n)이어도 전체 코드는 O(n²)일 수 있습니다
현재 구간을 직접 보고 싶어서 반복문 안에서 다음 코드를 실행한다고 하겠습니다.
const window = items.slice(left, right)이 코드는 경계 숫자 두 개만 보관하는 것과 다릅니다. 해당 구간의 원소를 담는 새 배열을 만듭니다.
모든 원소가 서로 다르면 구간 길이가 1, 2, 3 순서로 증가합니다. 매번 구간을 복사하면 복사하는 원소 수의 합이 O(n²)이 됩니다. 경계가 한 방향으로 움직인다는 사실만으로 이 비용까지 없어지지는 않습니다.
길이만 필요하다면 right - left로 계산합니다. 실제 구간을 반환해야 한다면 가장 좋은 구간의 시작과 끝만 기록한 뒤 마지막에 한 번 복사할 수 있습니다.
반복문 안에서 현재 구간 전체를 출력하거나 직렬화하는 작업도 같은 관점으로 살펴봐야 합니다. 알고리즘의 복잡도는 포인터 이동뿐 아니라 반복문 안에서 실행하는 모든 작업을 포함합니다.
배열 앞부분을 실제로 제거할 필요는 없습니다
왼쪽 경계를 이동할 때마다 입력 배열의 첫 원소를 제거하는 구현은 피하겠습니다. 일반적인 배열에서는 앞부분 삭제가 남은 원소의 인덱스 이동 비용을 만들 수 있습니다. 특정 실행 엔진의 최적화에 기대어 그 비용을 항상 O(1)이라고 가정할 수는 없습니다.
입력 배열을 변경하면 원래 인덱스와 마지막 등장 위치 사이의 관계도 유지하기 어려워집니다. 이 문제는 배열을 잘라내야 하는 문제가 아니라, 어느 범위를 현재 구간으로 볼지 정하는 문제입니다.
배열은 그대로 두고 left만 증가시키면 됩니다. 구간 밖의 원소가 입력 배열에 남아 있어도 현재 답을 계산할 때 포함하지 않으면 됩니다.
현재 구간과 전체 이력의 메모리를 구분합니다
마지막 등장 위치를 저장한 Map은 현재 구간이 짧다고 해서 함께 작아지지 않습니다. 구간 밖으로 나간 값의 과거 위치도 보관하기 때문입니다.
예를 들어 [1, 1, 2, 2, 3, 3]처럼 새로운 값이 두 번씩 등장하는 패턴을 계속 이어 보겠습니다. 가장 긴 중복 없는 구간은 길이 2에 머무르지만, Map에 저장하는 서로 다른 값의 개수는 계속 증가합니다.
길이가 최대 20만인 이번 입력에서는 O(d) 공간을 계산해 선택할 수 있습니다. 그러나 입력이 끝없이 들어오는 형태라면 전체 이력을 계속 보관하는 설계가 적절한지 다시 판단해야 합니다.
현재 구간의 값만 필요한 상황에서는 Set 방식이 이력 저장을 줄일 수 있습니다. 다만 모든 값이 서로 다른 입력에서는 현재 구간 자체가 계속 길어지므로, 이 방식도 임의의 입력에 대해 고정된 메모리만 사용하지는 않습니다.
호출이 끝나면 문제별 상태도 끝나야 합니다
lastSeen , left, right, best를 여러 테스트에서 공유하면 이전 입력의 상태가 다음 입력에 섞일 수 있습니다.
이전 호출에서 기록한 인덱스는 이전 배열의 위치입니다. 새로운 배열에서는 다시 인덱스 0부터 시작하므로 같은 위치 정보로 해석하면 안 됩니다.
모범답안에서는 이 상태를 함수 안에서 생성합니다. 같은 함수가 여러 번 호출되어도 각 입력을 독립적으로 처리하기 위해서입니다.
만약 입력을 여러 조각으로 나누어 이어서 처리하는 문제라면 상태를 유지해야 합니다. 그 경우에는 인덱스도 전체 입력 기준으로 이어져야 합니다. 독립된 테스트와 하나의 입력을 나누어 전달한 상황을 구분해야 합니다.
모든 연속 구간 문제에 같은 축소 규칙을 적용하지 않습니다
이번 문제에서 중복이 생긴 구간은 오른쪽에 다른 원소를 추가해도 중복이 없어지지 않습니다. 이미 들어 있는 중복 원소를 제외해야 유효해집니다. 반대로 중복이 없는 구간에서 왼쪽 원소를 제거하면 계속 중복이 없습니다.
이 성질 때문에 왼쪽 경계를 되돌리지 않고 앞으로만 이동할 수 있습니다. 더 긴 답을 찾기 위해 이미 제외한 시작점으로 돌아갈 필요가 없습니다.
조건이 바뀌면 이 성질도 다시 확인해야 합니다. 합이 3 이하인 가장 긴 연속 구간을 찾는 문제에서 다음 입력을 보겠습니다.
[4, -2, 1]
앞의 4만 보면 합이 3을 넘습니다. 그 순간 4를 제거하고 다시 포함하지 않으면 전체 구간을 놓칩니다. 전체 합은 3이고 정답 길이는 3이기 때문입니다.
음수가 있으면 오른쪽으로 확장했을 때 합이 줄어들 수 있습니다. 현재 조건을 위반한 구간이 앞으로도 계속 조건을 위반한다고 가정할 수 없습니다.
합을 기준으로 한 다른 문제에 같은 코드를 적용하기 전에, 원소를 추가하거나 제거했을 때 조건이 어떻게 변하는지 설명해야 합니다. 구간 문제라는 이유만으로 슬라이딩 윈도우의 이동 규칙이 결정되지는 않습니다.
시간 구간에서는 포함하는 경계를 다시 정합니다
배열에서 선택한 [left, right) 규칙을 시간 기반 문제에 그대로 적용해서는 안 됩니다. 시간 기반 문제에서도 어느 시점의 이벤트를 포함하는지 먼저 정해야 합니다.
예를 들어 현재 시각 t를 포함하고, 정확히 W초 전인 시각은 제외하기로 했다고 가정하겠습니다. 허용하는 범위는 t - W < eventTime <= t입니다.
현재 시각이 100이고 W가 10이라면 시각 90의 이벤트는 제외하고 시각 100의 이벤트는 포함합니다. 이 정의에서 만료 조건은 eventTime <= t - W입니다. 만료 검사에 <만 사용하면 왼쪽 경계 위의 이벤트가 하나 더 남을 수 있습니다.
또한 큐의 앞에서 오래된 이벤트를 제거하려면 시간 순서가 유지된다는 전제가 필요합니다. 이벤트가 시간순으로 들어오지 않는다면, 큐의 앞부분만 보고 만료된 이벤트를 모두 제거했다고 판단할 수 없습니다.
이번 배열 문제에서는 입력 인덱스가 순서를 정의합니다. 시간이나 다른 기준으로 순서를 바꾸는 문제에서는 경계의 포함 관계와 입력 순서의 보장을 함께 다시 확인해야 합니다.
모범답안
마지막 등장 위치를 사용한 구현
현재 값의 이전 위치가 현재 구간 안에 있을 때만 왼쪽 경계를 이동하겠습니다. 경계를 조정한 뒤 현재 위치를 기록하고, 오른쪽 경계를 증가시켜 새 값을 포함합니다.
function longestUniqueWindow(items) {
const lastSeen = new Map()
let left = 0
let right = 0
let best = 0
while (right < items.length) {
const value = items[right]
const previous = lastSeen.get(value)
if (previous !== undefined && previous >= left) {
left = previous + 1
}
lastSeen.set(value, right)
right += 1
best = Math.max(best, right - left)
}
return best
}lastSeen은 이미 처리한 전체 범위에서 각 값의 가장 최근 인덱스를 저장합니다. 현재 구간의 원소만 저장하는 자료구조가 아닙니다. 이 차이 때문에 previous >= left라는 확인이 필요합니다.
lastSeen.set(value, right)는 right를 증가시키기 전에 실행합니다. 현재 원소의 실제 인덱스를 기록해야 하기 때문입니다. 반대로 길이는 right를 증가시킨 뒤 계산합니다. 이때는 새 원소까지 포함한 구간이 [left, right)로 표현됩니다.
같은 변수라도 어느 시점의 상태인지 확인해야 합니다. 현재 원소의 위치를 기록하는 시점과, 새 원소를 포함한 구간의 길이를 계산하는 시점을 구분하면 한 칸 차이 오류를 줄일 수 있습니다.
실제 입력에서 경계를 따라가겠습니다
입력은 [1, 2, 2, 1, 3]입니다. 시작할 때 left, right, best는 모두 0입니다. 현재 구간 [0, 0)은 비어 있습니다.
인덱스 0의 값 1은 이전에 등장하지 않았습니다. 위치 0을 기록하고 right를 1로 증가시킵니다. 현재 구간은 [0, 1)이고 값은 [1]입니다. best는 1이 됩니다.
인덱스 1의 값 2도 이전에 등장하지 않았습니다. 처리 후 구간은 [0, 2)이고 값은 [1, 2]입니다. best는 2가 됩니다.
인덱스 2의 값 2는 이전 위치가 1입니다. 이 위치는 현재 구간 안에 있으므로 left를 2로 이동합니다. 새 위치를 기록하고 오른쪽 경계를 증가시키면 구간은 [2, 3)입니다. 길이는 1이므로 best는 2를 유지합니다.
인덱스 3의 값 1은 이전 위치가 0입니다. 현재 left는 2이므로 이 위치는 구간 밖에 있습니다. 왼쪽 경계를 유지한 채 새 위치를 기록합니다. 처리 후 구간은 [2, 4)이고 값은 [2, 1]입니다. best는 계속 2입니다.
인덱스 4의 값 3은 이전에 등장하지 않았습니다. 처리 후 구간은 [2, 5)이고 값은 [2, 1, 3]입니다. 길이가 3이므로 best를 3으로 갱신합니다.
이제 right가 배열 길이와 같으므로 반복문을 종료하고 3을 반환합니다. right가 5라는 이유로 인덱스 5의 원소를 읽지는 않습니다.
이 코드가 정답을 놓치지 않는 이유
반복문 시작 시 유지되는 조건을 먼저 정리하겠습니다. 실행 중 계속 참으로 유지해야 하는 이런 조건을 불변식이라고 부릅니다.
[left, right)에는 중복이 없습니다.
현재 오른쪽 경계에 대해 left는 유효한 구간을 만들 수 있는 가장 작은 시작점입니다.
lastSeen에는 인덱스 0부터 right - 1까지 처리한 값의 마지막 위치가 기록되어 있습니다.
best에는 지금까지 처리한 원소들로 만들 수 있는 최대 길이가 저장되어 있습니다.
시작할 때 구간은 비어 있습니다. 빈 구간에는 중복이 없고 최대 길이는 0이므로 이 조건들을 만족합니다.
새 값의 이전 위치가 없거나 left보다 작다면 현재 구간에는 같은 값이 없습니다. 그대로 추가해도 중복이 생기지 않습니다. 이전에 유효하지 않아 제외했던 더 왼쪽의 시작점들은 원소를 하나 더 추가한다고 다시 유효해지지 않으므로, 기존 left가 계속 가장 작은 유효 시작점입니다.
새 값의 이전 위치가 현재 구간 안의 previous라면, previous 이하에서 시작하는 구간은 이전 값과 새 값을 함께 포함합니다. 따라서 새로운 유효 구간은 적어도 previous + 1에서 시작해야 합니다.
그 위치로 이동하면 새 값과 중복되는 이전 원소가 제외됩니다. 나머지 원소들은 원래 중복이 없는 구간의 일부였으므로 새로운 중복이 생기지 않습니다. 더 오른쪽으로 이동할 필요도 없습니다.
따라서 매번 현재 원소에서 끝나는 유효한 구간 중 가장 긴 구간을 계산합니다. 모든 오른쪽 끝을 차례로 처리하고 그중 최대 길이를 저장하므로 전체 정답을 얻습니다.
빈 입력에서는 반복문이 한 번도 실행되지 않습니다. 초기값 0을 반환하므로 별도의 예외 처리 없이 문제의 정의를 만족합니다.
현재 구간만 저장하는 다른 모범답안
마지막 위치로 바로 이동하는 방식이 아직 익숙하지 않다면, 왼쪽 원소를 하나씩 제거하는 방식으로 구현할 수 있습니다.
function longestUniqueWindowWithSet(items) {
const seen = new Set()
let left = 0
let right = 0
let best = 0
while (right < items.length) {
const value = items[right]
while (seen.has(value)) {
seen.delete(items[left])
left += 1
}
seen.add(value)
right += 1
best = Math.max(best, right - left)
}
return best
}이 구현에서 seen은 현재 구간에 포함된 값만 저장합니다. 반복문 시작 시 현재 구간에는 중복이 없으므로, items[left]를 제외하면 그 값은 구간에 더 이상 존재하지 않습니다. 따라서 seen.delete(items[left])가 실제 구간의 변화와 일치합니다.
새 값이 seen에 남아 있는 동안 계속 왼쪽 원소를 제거합니다. 기존의 같은 값이 제거되는 순간 안쪽 반복문이 종료됩니다. 그 뒤 새 값을 추가하면 다시 중복 없는 구간이 됩니다.
두 구현은 같은 경계 원칙을 사용합니다. Map 구현은 마지막 위치를 이용해 한 번에 이동하고, Set 구현은 조건이 회복될 때까지 순서대로 이동합니다. 평균 시간 복잡도는 모두 O(n)이며, 어떤 상태를 저장하는지와 추가 공간의 범위가 다릅니다.
반례를 조건별로 선택합니다
다음 입력들은 각각 다른 오류를 드러냅니다.
longestUniqueWindow([]) // 0
longestUniqueWindow([7]) // 1
longestUniqueWindow([7, 7]) // 1
longestUniqueWindow([1, 2, 2, 1]) // 2
longestUniqueWindow([1, 2, 3, 2, 4, 5]) // 4빈 배열은 초기 상태와 종료 조건을 확인합니다. 원소 하나인 배열은 길이 계산이 한 칸 어긋나지 않는지 확인합니다.
[7, 7]은 이전 위치가 0일 때도 중복으로 처리하는지, 왼쪽 경계 위의 원소를 포함하는지 확인합니다. 이 입력은 참과 거짓으로 위치를 판단하는 오류와 등호를 빠뜨린 오류를 함께 드러낼 수 있습니다.
[1, 2, 2, 1]은 구간 밖의 과거 위치 때문에 왼쪽 경계가 뒤로 이동하는지 확인합니다. [1, 2, 3, 2, 4, 5]는 구간 전체를 버리는 오류와 한 번만 제거하는 오류를 확인합니다.
서로 다른 값만 있는 배열은 전체 길이를 답으로 선택할 수 있는지 확인합니다. 0과 음수가 있는 배열은 값의 부호나 0 여부를 임의의 종료 조건으로 사용하지 않는지 확인합니다. 두 값이 번갈아 나오는 배열은 경계를 여러 차례 이동한 뒤에도 같은 규칙이 유지되는지 확인합니다.
면접에서 풀이를 설명하는 순서
설명은 자료구조 이름보다 구간의 정의에서 시작하겠습니다.
현재 구간을 왼쪽은 포함하고 오른쪽은 제외하는 [left, right)로 두겠습니다. 반복문이 시작될 때 이 구간에는 중복이 없습니다. 다음 값이 현재 구간에 이미 있다면 이전 위치 다음으로 왼쪽 경계를 이동합니다. 이전 위치가 구간 밖에 있으면 경계를 유지합니다.
이어서 정답을 갱신하는 시점을 설명합니다. 중복을 해소하고 새 원소를 포함한 뒤 right - left를 계산하겠습니다. 이전에 확인한 최대 길이와 비교하면 됩니다.
복잡도는 원소를 처리하는 횟수로 설명합니다. 오른쪽 경계가 입력 전체를 한 번 순회하고, 마지막 위치를 평균 O(1)에 조회하고 갱신한다고 가정하므로 평균 시간은 O(n)입니다. 서로 다른 값의 수만큼 마지막 위치를 저장하므로 추가 공간은 O(d)입니다.
면접관이 previous >= left가 왜 필요한지 물으면 [1, 2, 2, 1]을 사용할 수 있습니다. 이미 구간 밖으로 나간 값 때문에 왼쪽 경계를 되돌리면 중복을 다시 포함하기 때문입니다. 등호의 이유는 [7, 7]로 설명할 수 있습니다. 이전 값이 왼쪽 경계에 정확히 놓여 있어도 현재 구간에 포함되기 때문입니다.
이 문제에서 유지해야 하는 것은 중복 없는 구간과 한 방향으로 이동하는 경계입니다. 구간의 포함 관계를 먼저 정하고, 유효성을 회복한 뒤 길이를 계산하면 구현과 정당성 설명을 같은 규칙으로 이어갈 수 있습니다.