문제
https://www.acmicpc.net/problem/11003
11003번: 최솟값 찾기
N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.
www.acmicpc.net
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main11003 {
static int N,L;
static Deque<Node> dq;
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());
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
dq = new LinkedList<Node>();
for (int i=0; i<N; i++) {
int temp = Integer.parseInt(st.nextToken());
while (!dq.isEmpty() && dq.getLast().val > temp) {
dq.removeLast();
}
dq.addLast(new Node(temp, i));
if (dq.getFirst().idx <= i - L) {
dq.removeFirst();
}
bw.write(dq.getFirst().val + " ");
}
bw.flush();
bw.close();
}
static class Node {
private int val;
private int idx;
public Node(int val, int idx) {
this.val = val;
this.idx = idx;
}
}
}
1. 덱이라는 자료구조를 이용하면 어렵지 않게 풀 수있다. 덱을 몰라 List로만 하려다보니 계속 애를 먹었다.
2. 덱의 마지막 부터 탐색을 할 때, 새로들어올 숫자가 기존에 있는 숫자보다 작을 경우 마지막 인덱스의 아이템을 삭제한다.
그 다음 덱이 가지고 있는 아이템들의 인덱스 범위가 L을 초과할 경우 덱의 첫번째 아이템을 제거한다.
3. 그 다음 출력해주면 끝.
정리 : 덕분에 Deque라는 자료구조 하나 공부했다.
'백준' 카테고리의 다른 글
백준 17298번 자바 ☆ (0) | 2023.01.04 |
---|---|
백준 1874번 자바 (0) | 2023.01.03 |
백준 12891번 자바 (0) | 2022.12.31 |
백준 1253번 자바 ☆ (0) | 2022.12.30 |
백준 1940번 자바 (0) | 2022.12.29 |