3-10. [슬라이딩 윈도우] 최솟값 찾기 1

최솟값 찾기

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2.4 초 (하단 참고)

512 MB

22207

6450

4112

29.409%

문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

예제 입력 1 복사

12 3
1 5 2 3 6 2 3 7 3 5 2 6

예제 출력 1 복사

1 1 1 2 2 2 2 2 3 3 2 2

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: doju

시간 제한

• Java 8: 2.6 초
• Java 8 (OpenJDK): 2.6 초
• Java 11: 2.6 초
• Kotlin (JVM): 2.6 초

---

풀이

1. [인덱스, 값]의 구조로 저장한다.
2. [[1, 1], [2, 5]] 일 경우 => 
3. [[1, 1], [2, 5], [3, 2]] 일 경우 => 5 > 2 이기 때문에 [2, 5]를 지운다 => 최솟값은 1 < 2 < 5 이므로 [1, 1, 1]이다 => 덱에서는 [2, 5]를 지우고 [[1, 1], [3, 2]]을 남긴다
4. [[1, 1], [3, 2], [4, 3]] 일 경우 => L의 값이 3(윈도우)이기 때문에 => 4 - 3 > 0 이기 때문에 맨 앞의 것을 지운다(윈도우를 옮기는 과정) => 따라서 [[3, 2], [4, 3]]에서 생각하면 => 최솟값은 3 > 2 이라면 => [1, 1, 1, 2] 이다
5. 이렇게 반복한다.

코드

let N = 12;
let L = 3;
const mydeque = [];
let now = [1, 5, 2, 3, 6, 2, 3, 7, 3, 5, 2, 6];
const result = [];

for (let i = 0; i < N; i++) {
  // 새로운 값이 들어올 때마다 정렬 대신
  // 현재 수보다 큰 값을 덱에서 제거해서
  // 시간 복잡도를 줄임

  while (mydeque.length > 0 && mydeque[mydeque.length - 1][0] > now[i]) {
    mydeque.pop();
  }

  mydeque.push([now[i], i]);
  if (mydeque[0][1] <= i - L) {
    mydeque.shift();
  }

  result.push(mydeque[0][0]);
}

console.log("result: ", result);