배열을 입력받아, 서로 다른 숫자가 최대 2개까지만 포함된 가장 긴 부분 배열(슬라이스)을 반환하는 함수를 작성해야 한다고 가정해 보겠습니다. 이 문제를 자세히 살펴보면, 안정적인(stable) 하위 배열을 검사하면서 원본 배열을 순회하는 방식으로 접근해야 함을 알 수 있습니다.
이러한 유형의 문제에는 슬라이딩 윈도우(Sliding Window) 알고리즘이 특히 적합합니다. 윈도우의 시작점(start)과 끝점(end)을 조절하면서 조건을 만족하는 구간을 효율적으로 탐색할 수 있기 때문입니다. 슬라이딩 윈도우 알고리즘으로 이 문제를 해결한 코드는 다음과 같습니다.
예제
const arr = [1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8, 1, 1 ,1 ,1, 8, 1,
1, 8, 8];
const map = {
length: 0
};
let required = [];
for(start = 0, end = 0; end <= arr.length; ){
if(map.length > 2){
if(map[arr[start]] === 1){
delete map[arr[start]];
map.length --;
}else{
map[arr[start]]--;
};
start++;
}else{
if(end - start > required.length){
required = arr.slice(start, end);
};
if(map[arr[end]]){
map[arr[end]]++;
}else{
map[arr[end]] = 1;
map.length++;
}
end++;
}
}
console.log(required);코드 설명
이 코드의 핵심 동작 원리는 다음과 같습니다.
- 빈도 맵 유지: 현재 윈도우 범위 내에 있는 각 숫자의 등장 횟수를 객체(map)에 저장하고, 서로 다른 숫자의 종류 수는 별도의 length 속성으로 추적합니다.
- 최장 구간 갱신: 매 반복마다 현재 윈도우의 길이(end - start)를 기존에 저장된 최장 부분 배열의 길이와 비교하여, 더 길다면 slice() 메서드로 해당 구간을 새로 저장합니다.
- 조건 위반 시 윈도우 축소: 서로 다른 숫자의 개수가 2개를 초과하면, 왼쪽 끝(start)의 요소를 하나씩 제거하며 윈도우를 오른쪽으로 밀어 다음 안정적인 구간을 탐색합니다.
이러한 방식 덕분에 모든 가능한 부분 배열을 일일이 검사하는 브루트 포스 방식(O(n²))보다 훨씬 효율적인 O(n) 시간 복잡도로 문제를 해결할 수 있습니다.
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[
1, 8, 1, 1, 1,
1, 8, 1, 1, 8,
8
]출력된 배열은 원본 배열에서 서로 다른 숫자(1과 8) 두 개만으로 구성된 가장 긴 연속 구간입니다.