N개의 수 A1, A2, ..., AN과 L이 주어진다. Ai-L+1 ~ Ai중 최솟값을 Di라고 할 때 D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때 i ⪯ 0 인 Ai는 무시하고 D를 구해야 한다.
입력
1번째 줄에 N과 L(1 ⪯ L ⪯ N ⪯ 5,000,0000), 2번째 줄에 N개의 수 Ai가 주어진다.(-109 ⪯ Ai ⪯ 109).
출력
1번째 줄에 Di를 공백으로 구분해 순서대로 출력한다.
예제 입력
12 3 // 숫자의 개수, 슬라이딩 윈도우의 크기
1 5 2 3 6 2 3 7 3 5 2 6
예제 출력
1 1 1 2 2 2 2 2 3 3 2 2
1단계 - 문제 분석하기
일정 범위 안에서 최솟값을 구하는 문재이므로 슬라이딩 윈도우와 정렬을 사용. 윈도우의 크기는 최솟값을 구하는 범위가 i-L+1 ~ i 이므로 L로 생각하면 된다.
일반적인 정렬은 O(nlogn)의 시간 복잡도를 가지므로 최대 범위가 5,000,000인 이 문제에선 정렬을 사용할 수 없다. 이 문제에선 O(n)의 시간 복잡도로 해결해야 한다.
슬라이딩 윈도우를 덱(deque)으로 구현하면 정렬 효과를 볼 수 있다.
덱은 양 끝에서 데이터를 삽입하거 삭제할 수 있는 자료구조이다.
2단계 - 손으로 풀어 보기
1 덱에서는 (인덱스, 숫자) 형태의 노드를 클래스로 구현하여 저장한다. (1, 1), (2, 5)를 덱에 추가하는 과정은 생략하였다.
2 이 상태에서 새 노드 (3, 2)가 덱에 저장된다. 여기부터 기존 덱에 있던 노드가 제거된다.
새 노드 (3, 2)가 저장될 때 뒤의 노드부터 비교를 시작한다. (2, 5)는 (3, 2)보다 숫자가 크므로 (2, 5)는 덱에서 제거(removeLast())한다.
이어서 (1, 1)은 (3, 2)보다 숫자가 작으므로 탐색을 멈추고 (3, 2)를 덱에 저장(addLast())한다.
결과를 보면 (2, 5)노드가 제거되었고, 노드가 오름차순으로 정렬되어 있다.
정리가 된 상태의 덱을 보면 인덱스 범위가 1 ~ 3 이므로 최솟값을 찾아도 된다. 최솟값은 덱 처음에 있는 (1, 1) 노드이다
3 계속해서 새 노드를 추가한다. 이번에는 인덱스 범위가 슬라이딩 윈도우 범위를 벗어난 예이다.
새 노드 (4, 3)은 덱 맨 뒤에서부터 비교했을 때 (3, 2)보다 숫자가 크므로 덱에 저장된다.
여기서 인덱스 범위에 의해 덱 맨 앞쪽의 노드가 제거된다. (1, 1), (3, 2), (4, 3)의 인덱스 범위는 1 ~ 4 이므로 윈도우 범위인 3을 벗어난다. 최솟값은 윈도우 범위 내에서 찾기로 했으므로 (1, 1)은 덱에서 제거해야 한다. 제거가 끝난 이후에 최솟값을 출력하면 2이다.
4 다시 정리하면 숫자 비교, 윈도우 범위 계산이 끝난 덱에서 맨 앞에 있는 노드의 숫자를 출력하기만 하면 정답이 된다.
3단계 - sudo코드 작성하기
N(데이터 개수), L(최솟값을 구하는 범위)
Deque<Node> mydeque(데이터를 담을 덱 자료구조)
for(N만큼 반복) {
now(현재 데이터 값)
덱의 마지막 위치에서부터 now보다 큰 값은 덱에서 제거하기
덱의 마지막 위치에 now 값 저장하기
덱의 1번째 위치부터 L의 범위를 벗어난 값(now index - L <= index)을 덱에서 제거하기
덱의 1번째 데이터 출력하기
}
덱에 저장할 노드 클래스 별도 생성하기
노드 클래스에는 index(자신의 위치), value(자신의 값) 담기4단계 - 코드 구현하기
import java.io.*;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Q10 {
public static final Scanner sc = new Scanner(System.in);
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int L = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
Deque<Node> mydeque = new LinkedList<>();
for(int i = 0; i < N; i++){
int now = Integer.parseInt(st.nextToken());
while(!mydeque.isEmpty() && mydeque.getLast().value > now){
mydeque.removeLast();
}
mydeque.addLast(new Node(i, now));
if(mydeque.getFirst().index <= i-L){
mydeque.removeFirst();
}
bw.write(mydeque.getFirst().value + " ");
}
bw.flush();
bw.close();
}
static class Node{
public int index;
public int value;
Node(int index, int value){
this.index = index;
this.value = value;
}
}
}
- Do it! 알고리즘 코딩테스트 자바 편
