[백준 플레티넘 5] 11003번: 최솟값 찾기

문제

https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

 

 

풀이

• N개의 수열과 L이 주어진다. 수열의 연속된 숫자 L개 중에서 최솟값을 D라고 할 때, 최솟값들을 구해야 한다.
• 예를 들어 5개의 수열 1, 2, 3, 4, 5와 L = 3가 주어질 때, (1, 2, 3), (2, 3, 4), (3, 4, 5) 중에 최솟값을 구해서 출력해야 한다. ( 1 2 3 이런식으로)
• N과 L의 범위가 1 이상 5,000,000 이하이므로 정렬을 사용하지 않고 문제를 풀어야 한다.

 

L 범위의 숫자를 정렬된 상태로 계속 관리하기 위해서는 맨 앞과 맨 뒤에서 데이터를 삽입하고 삭제할 수 있어야 한다. 그렇기 때문에 양 끝 모두에서 데이터를 관리할 수 있는 Deque 자료구조를 사용하였다.

 

Deque는 기본적으로 큐의 구조를 가지되 좀 더 편의성을 높인 자료구조이다. addFirst(), addLast, removeFirst(), removeLast() 등 Deque가 제공하는 함수들을 사용하였다.

Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1);
deque.addLast(2);
deque.removeFirst();
deque.removeLast();

 

 

index와 value를 멤버로 가지는 클래스 Node를 선언한다. index는 범위 L을 유지하기 위해, 그리고 value는 크기를 비교하며 정렬을 유지하기 위해 사용한다. 콘솔창에서 출력 결과를 확인하기 위한 toString() 메서드도 정의하였다.

class Node {
    int index;
    int value;

    public Node(int index, int value) {
        this.index = index;
        this.value = value;
    }

    public String toString() {
        return index + " " + value;
    }
}

 

 

핵심은 정렬 기능을 사용하지 않고 Deque의 값을 오름차순 상태로 유지하는 것이다. 이때, 첫번째 값이 제일 작으므로 최소값이 된다.

새로운 값이 Deque의 마지막 값보다 작다면, Deque의 마지막 값을 삭제하고 새로운 값을 입력하는 것으로 오름차순 상태를 유지할 수 있다.

while (!deque.isEmpty() && deque.getLast().value > target) {
    deque.removeLast();
}
deque.addLast(new Node(i, target));

 

 

그리고 L의 범위를 계속 유지해야 한다. 현재 i와 Deque의 첫번째 Node의 index를 비교하며 범위 L보다 바깥인 경우 맨 처음 Node를 삭제하여 Deque의 크기를 유지시킨다.

if(deque.getFirst().index <= i - L) {
    deque.removeFirst();
}

 

이런 과정을 거쳐 Deque의 맨 처음 값이 바로 최솟값이 된다.

 

전체 코드 (Java)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());

		StringBuilder sb = new StringBuilder();
		Deque<Node> deque = new LinkedList<>();
		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			int target = Integer.parseInt(st.nextToken());

			// deque을 이용한 정렬, 새로운 값이 덱의 마지막 값보다 작다면 마지막 값을 삭제하고 새 값을 추가한다.
			while (!deque.isEmpty() && deque.getLast().value > target) {
				deque.removeLast();
			}
			deque.addLast(new Node(i, target));
			
			// 범위 L을 벗어나면 제일 앞의 값을 제거
			if(deque.getFirst().index <= i - L) {
				deque.removeFirst();
			}
			
//			System.out.println(deque);

			// 최종적으로 덱은 계속 오름차순 정렬된 상태이므로 맨 앞의 값이 최소값이 된다.
			sb.append(deque.getFirst().value).append(" ");
		}
		
		System.out.println(sb);
	}

	static class Node {
		int index;
		int value;

		public Node(int index, int value) {
			this.index = index;
			this.value = value;
		}
		
		public String toString() {
			return index + " " + value;
		}
	}

}

 

 

후기

Deque를 평소에 많이 사용해보지 않았는데 양 끝의 데이터를 모두 관리할 수 있어서 편하게 느껴졌다. 앞으로 좀 더 능숙하게 사용할 수 있도록 연습해봐야겠다.