[완전탐색 피하기] 덱(deque)

길이가 N인 배열 arr에서 arr[i-L+1]~arr[i] 중 최소값을 answer[i]이라고 할 때, answer 구하기

(백준 온라인 저지 11003)

arr for문을 돌면서, 0~L-1까지 for문을 또 돌리면서 최소값을 찾음 O(N*L)

var answer = [];
for (var i=0; i<arr.length; i++) {
	var min = arr[i];
	for (var j=i; j>=i-L+1; j--) {
    	if (j<0) continue;
        if (arr[j] < min) {
        	min = arr[j];
        }
    }
    answer.push(min);
}

 

덱은 큐처럼 넣고 빼는데, 양 끝에서 넣고 빼는 구조.

push/pop처럼 unshift/shift

 

일단 arr for문을 돌면서 deque에 넣는다. 넣는데,,

arr[i]는 반드시 최소값 판정에 사용해야 하니까 반드시 넣어야 함.(push)

deque의 뒷부분 부터 검사 하는데,

맨뒤값 보다 arr[i]가 작으면, 앞으로 최대 L턴 동안은 arr[i] 쓸모가 있을지도?

반대로 맨뒤값은 쓸모 없어짐.(최소값을 구하는거니까)

뒤부터 검사하면서 arr[i]가 작으면 계속 pop.

다 쳐냈으면 arr[i] push.

L이라는 길이 제한이 있으니까,

들어올 arr[i] 인덱스 i랑 deque 첫번째 값의 인덱스(arr 있을 적 index) 차이가 L을 벗어나면 shift.

각 최소값은 그때의 deque의 첫번째 값임.

var deque = [];
for (var i=0; i<arr.length; i++) {
    while (deque.length && deque[deque.length-1][0] > arr[i]) {
        deque.pop();
    }

    deque.push([arr[i], i]);
    if (deque[0][1] <= i - L) {
        deque.shift();
    }
    console.log(deque[0][0]);
}

값, 인덱스 둘다 필요하기 때문에, deque에 [값, 인덱스] 통째로 push.