💡 문제
continuous-subarrays (https://leetcode.com/problems/continuous-subarrays/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.
📝 선행 개념
1. 슬라이딩 윈도우 (Sliding Window)
정의: 슬라이딩 윈도우는 배열이나 리스트와 같은 선형 데이터 구조에서 일정한 크기의 부분을 이동하면서 문제를 해결하는 기법입니다.
활용:
- 주어진 범위 내에서 연속적인 부분 배열을 찾거나 특정 조건을 만족하는 부분 배열을 효율적으로 처리할 때 사용합니다.
- 두 포인터(start와 end)를 사용하여 현재 고려 중인 윈도우를 나타내고, 이 범위를 확장하거나 축소하여 문제를 해결합니다.
2. 스택 (Deque - Double Ended Queue)
정의: 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐입니다. Java에서 Deque 인터페이스를 구현한 LinkedList 클래스를 사용할 수 있습니다.
활용:
- 슬라이딩 윈도우 내에서 최대값 또는 최소값을 효율적으로 추적하는 데 사용됩니다.
- maxDeque와 minDeque를 사용하여 현재 윈도우 내의 최대값과 최소값을 유지할 수 있습니다.
- offerLast, pollLast, peekFirst, peekLast와 같은 메소드를 통해 덱을 조작합니다.
🤓 문제 풀이
🔨 문제 설명
주어진 문제는 주어진 배열 nums에서 특정 조건을 만족하는 연속적인 부분배열의 개수를 찾는 것입니다. 주어진 조건은 다음과 같습니다:
- 임의의 두 인덱스 i1,i2에 대해, 부분배열 [i,j] 내의 모든 요소들 nums[i1],nums[i2] 사이의 절대값 차이가 2 이하이어야 합니다.[i,j][i, j]
- nums[i1],nums[i2]nums[i1], nums[i2]
- i1,i2i1, i2
🔨 접근 방법
- 슬라이딩 윈도우 기법: 이 문제를 해결하기 위해 슬라이딩 윈도우 기법을 사용합니다. 이는 부분배열의 시작점을 기준으로 윈도우를 확장하거나 축소하여 조건을 만족하는 부분배열의 수를 세는 방법입니다.
- 부분배열 개수 세기: 각 요소를 부분배열의 시작점으로 고려하며, 윈도우를 확장시키며 조건을 만족시킬 때마다 윈도우의 크기에 따라 유효한 부분배열의 수를 계산합니다.
🔨 문제 풀이 과정
- 초기화:
- count: 유효한 부분배열의 총 개수를 세는 변수입니다.
- start: 현재 유효한 부분배열의 시작 인덱스를 나타내는 변수입니다.
- 배열 순회:
- 각 인덱스 i를 시작점으로 하여, end를 i로 초기화하고 조건 |nums[end] - nums[start]| <= 2을 만족할 때까지 end를 확장합니다.
- 각 유효한 end에 대해, 해당 위치에서 끝나는 부분배열의 개수는 (end - start + 1)입니다.
- 이를 count에 누적합니다.
- 덱(deque) 사용: 최대값과 최소값을 유지하기 위해 각각 두 개의 덱을 사용합니다.
- maxDeque는 현재 윈도우 내의 최대값을 유지합니다.
- minDeque는 현재 윈도우 내의 최소값을 유지합니다.
- 슬라이딩 윈도우 조절:
- end 포인터를 오른쪽으로 이동시키면서 현재 윈도우를 확장합니다.
- maxDeque와 minDeque에 nums[end]를 추가하여 최대값과 최소값을 업데이트합니다.
- 만약 최대값과 최소값의 차이가 2를 초과하면, start 포인터를 오른쪽으로 이동시켜 윈도우를 축소합니다.
- 부분 배열 개수 계산:
- 각 end 위치에서 유효한 부분 배열의 개수를 (end - start + 1)로 계산하여 총 개수에 누적합니다.
🔨 슬라이딩 윈도우
슬라이딩 윈도우(Sliding Window) 기법이란?
슬라이딩 윈도우 기법은 배열이나 리스트와 같은 선형 데이터 구조에서 일정 범위를 유지하며 효율적으로 문제를 해결하기 위한 기법입니다. 이 기법은 두 개의 포인터(또는 인덱스)를 사용하여 현재 고려 중인 범위를 나타내고, 이 범위를 조절하면서 문제를 해결합니다. 슬라이딩 윈도우는 다음과 같은 과정으로 동작합니다:
- 초기화: 윈도우의 시작(start)과 끝(end)을 나타내는 두 포인터를 설정합니다.
- 확장: 윈도우의 끝 포인터를 이동시키며 윈도우를 확장합니다.
- 축소: 필요할 때 윈도우의 시작 포인터를 이동시켜 윈도우를 축소합니다.
- 조건 검사: 각 단계에서 윈도우의 조건을 검사하여 필요한 작업(예: 최대값 계산, 조건 만족 여부 검사 등)을 수행합니다.
슬라이딩 윈도우 기법의 장점은 중복 계산을 피하고 효율적으로 문제를 해결할 수 있다는 것입니다.
🔨 구현코드
import java.util.Deque;
import java.util.LinkedList;
class Solution {
public long continuousSubarrays(int[] nums) {
int n = nums.length;
long count = 0;
int start = 0;
// 최대값과 최소값을 유지하기 위한 덱
Deque<Integer> maxDeque = new LinkedList<>();
Deque<Integer> minDeque = new LinkedList<>();
for (int end = 0; end < n; end++) {
// 현재 요소를 덱에 추가하여 최대값과 최소값 유지
while (!maxDeque.isEmpty() && maxDeque.peekLast() < nums[end]) {
maxDeque.pollLast();
}
while (!minDeque.isEmpty() && minDeque.peekLast() > nums[end]) {
minDeque.pollLast();
}
maxDeque.offerLast(nums[end]);
minDeque.offerLast(nums[end]);
// 조건을 만족하지 않으면 start를 이동
while (maxDeque.peekFirst() - minDeque.peekFirst() > 2) {
if (maxDeque.peekFirst() == nums[start]) {
maxDeque.pollFirst();
}
if (minDeque.peekFirst() == nums[start]) {
minDeque.pollFirst();
}
start++;
}
// 현재 end까지 유효한 부분배열의 개수 추가
count += (end - start + 1);
}
return count;
}
}import java.util.Deque;
import java.util.LinkedList;
class Solution {
public long continuousSubarrays(int[] nums) {
int n = nums.length; // 배열의 길이
long count = 0; // 유효한 부분 배열의 총 개수
int start = 0; // 현재 유효한 부분 배열의 시작 인덱스
// 최대값과 최소값을 유지하기 위한 덱
Deque<Integer> maxDeque = new LinkedList<>();
Deque<Integer> minDeque = new LinkedList<>();
for (int end = 0; end < n; end++) {
// 현재 요소를 덱에 추가하여 최대값과 최소값 유지
while (!maxDeque.isEmpty() && maxDeque.peekLast() < nums[end]) {
maxDeque.pollLast();
}
while (!minDeque.isEmpty() && minDeque.peekLast() > nums[end]) {
minDeque.pollLast();
}
maxDeque.offerLast(nums[end]);
minDeque.offerLast(nums[end]);
// 조건을 만족하지 않으면 start를 이동
while (maxDeque.peekFirst() - minDeque.peekFirst() > 2) {
if (maxDeque.peekFirst() == nums[start]) {
maxDeque.pollFirst();
}
if (minDeque.peekFirst() == nums[start]) {
minDeque.pollFirst();
}
start++;
}
// 현재 end까지 유효한 부분 배열의 개수 추가
count += (end - start + 1);
}
return count;
}
}📚 풀이 보완
코드 설명
- Deque 사용: maxDeque와 minDeque 두 개의 덱을 사용하여 윈도우 내의 최대값과 최소값을 유지합니다.
- 윈도우 조정: end 포인터를 이동시키며 nums[end]를 덱에 추가하고, 최대값과 최소값의 차이가 2를 초과하면 start 포인터를 이동시켜 윈도우를 축소합니다.
- 부분배열 개수 누적: 각 end 위치에서 유효한 부분배열의 개수를 (end - start + 1)로 계산하여 count에 누적합니다.
스택 코드 설명
- 덱 초기화:
- maxDeque와 minDeque를 각각 LinkedList로 초기화하여 최대값과 최소값을 관리합니다.
- 윈도우 확장:
- for (int end = 0; end < n; end++) 루프에서 end 포인터를 이동시키며 윈도우를 확장합니다.
- 현재 요소 nums[end]를 덱에 추가하여 최대값과 최소값을 유지합니다.
- maxDeque는 요소를 내림차순으로 유지하기 위해, 현재 요소보다 작은 요소를 제거하고 추가합니다.
- minDeque는 요소를 오름차순으로 유지하기 위해, 현재 요소보다 큰 요소를 제거하고 추가합니다.
- 윈도우 축소:
- 최대값과 최소값의 차이가 2를 초과하면 start 포인터를 이동시켜 윈도우를 축소합니다.
- 이때, start 포인터가 가리키는 값이 덱의 첫 번째 값과 같다면 해당 값을 덱에서 제거합니다.
- 부분 배열 개수 계산:
- 각 end 위치에서 유효한 부분 배열의 개수를 (end - start + 1)로 계산하여 count에 누적합니다.
📍 Plus+
시간 복잡도
- 덱 업데이트: 각 요소는 덱에 한 번 추가되고, 한 번 제거되므로 각 덱의 연산은 O(1)입니다.
- 슬라이딩 윈도우: 배열의 각 요소에 대해 덱을 업데이트하고 윈도우의 시작점을 조정합니다.
- 시간 복잡도: O(n), 여기서 n은 배열 nums의 길이입니다. 배열의 각 요소를 한 번씩 처리하고, 각 연산이 상수 시간 내에 완료되기 때문입니다.
공간 복잡도
- 덱 사용: 최대값과 최소값을 추적하기 위해 두 개의 덱을 사용합니다. 각각의 덱은 최악의 경우 배열의 모든 요소를 포함할 수 있습니다.
- 공간 복잡도: O(n), 여기서 n은 배열 nums의 길이입니다. 이는 덱에 저장되는 요소의 개수가 배열의 크기와 비례하기 때문입니다.
요약
- 시간복잡도: O(n)
- 공간복잡도:O(n)