공부 기록

처음에는 단순하게 maxHeap을 이용해서 O(N)만에 풀면 되지 않을까 생각했다.

윈도우를 maxHeap에 넣고 움직이면서 맨 앞의 값은 빼고, 뒤에 새로 들어오는 값은 더해주는 방식으로 구현했다.

import java.util.*;
class Solution {
	public int[] maxSlidingWindow(int[] nums, int k) {
		int length = nums.length;
		int answer[] = new int[length - k + 1];

		PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
		for (int i = 0; i < k; i++) {
			maxHeap.add(nums[i]);
		}
		answer[0] = maxHeap.peek();

		for (int i = 1; i < length - k + 1; i++) {
			Integer remove = nums[i - 1];
			int add = nums[i + k - 1];
			maxHeap.remove(remove);
			maxHeap.add(add);

			answer[i] = maxHeap.peek();
		}

		return answer;
	}
}

결과는 Hard 문제 답게 TLE가 떴다...ㅠ

다시 문제 조건을 자세히 살펴봤다. 문제 조건은 아래와 같다.

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

내가 구현한 코드가 O(N)이 맞다면 nums.length<=10^5이기 때문에 시간내에 동작해야 했다.

다시 생각 해 보니 maxHeap에 넣고 빼는 동작이 logk씩 일어나기 때문에 O(NlogK)로 시간초과가 날 수 있다는 점을 생각하지 못했다.

뭔가 윈도우를 하나씩 옮기는 방법은 맞는 것 같으니, 최댓값을 구할 때 O(logK)보다 줄일 수 있는지 생각해 봤다.

일단은 문자열을 넣고 뺄때 힙구조가 아닌 Deque를 사용하는게 좋을 것 같았다. Deque는 맨앞과 맨뒤의 요소를 넣고 뺄 때 O(1)이 걸린다.

문제 풀이 방법은 아래와 같다.

1. 위의 경우와 마찬가지로 첫 k개는 Deque에 넣고 최댓값을 구한다.

2. 윈도우를 움직인다. 이 때,

• deque에는 index를 넣어두고, 현재 윈도우 안의 요소가 될 수 있는 인덱스들만 넣어 둔다.
• 새로 집어 넣는 값에 비해 작은 값들을 앞에서 부터 다 뺀다. 왜냐면 윈도우는 오른쪽으로 움직이고 있고, 현재 넣는 값보다 작은 기존의 deque에 있는 값은 영원히 최대값이 될 수 없기 때문이다.

아래는 구현한 코드이다.

import java.util.*;
class Solution {
	public void moveWindow(int i, int k, ArrayDeque<Integer> deque, int[] nums) {
		if (!deque.isEmpty() && deque.getFirst() == i - k) {
			deque.removeFirst();
		}

		while (!deque.isEmpty() && nums[i] > nums[deque.getLast()]) {
			deque.removeLast();
		}
	}

	public int[] maxSlidingWindow(int[] nums, int k) {
		ArrayDeque<Integer> deque = new ArrayDeque<Integer>();
		int length = nums.length;
		if (length * k == 0) {
			return new int[0];
		}
		if (k == 1) {
			return nums;
		}

		int maxIndex = 0;
		for (int i = 0; i < k; i++) {
			moveWindow(i, k, deque, nums);
			deque.addLast(i);

			if (nums[i] > nums[maxIndex]) {
				maxIndex = i;
			}
		}

		int[] answer = new int[length - k + 1];
		answer[0] = nums[maxIndex];

		for (int i = k; i < length; i++) {
			moveWindow(i, k, deque, nums);
			deque.addLast(i);
			answer[i - k + 1] = nums[deque.getFirst()];
		}
		return answer;
	}
}