오늘 풀어볼 문제는 백준 11003번 문제 "최솟값 찾기" 이다.
이 문제는 플래티넘5 문제이고 슬라이딩 윈도우 문제이다.
문제
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를 공백으로 구분하여 순서대로 출력한다.이 문제는 슬라이딩 윈도우 문제면서도 Deque를 활용해서 풀어야 하는 문제이다.
Deque에 대해 공부를 해보았다.
Deque
Double-Ended Queue의 줄임말로 큐의 양쪽으로 엘리먼트의 삽입과 삭제를 수행할 수 있는 자료구조를 의미한다.
자바에서의 덱은 인터페이스로 구현되었다. 덱 자료구조의 여러 연산들을 정의한 Deque 인터페이스가 있고 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있다.
Deque의 메서드는 인터넷에 치면 많이 나오니 ㅎㅎ 생략하겠다.
📌첫 번째 도전📌
앞 글에서 내 손으로 풀어보겠다 했는데... 플레 문제라 확실히 어렵기도 하고 Deque 처음 다뤄보아서 책을 보면서 풀었다... ㅎㅎ
생각보다 코드량을 문제 난의도에 비해 적었다. 자료구조를 이용해서 그런 것인가? 라는 생각도 했다.
for문을 돌리면서 조건에 맞게 추가하고 제거하는 로직으로 구현을 했다.
public class Main {
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> deque = new LinkedList<>();
for(int i=0; i<N; i++) {
int cur = Integer.parseInt(st.nextToken());
while (!deque.isEmpty() && deque.getLast().value > cur) {
deque.removeLast();
}
deque.addLast(new Node(cur, i));
if(deque.getFirst().index <= i - L) {
deque.removeFirst();
}
bw.write(deque.getFirst().value+ " ");
}
bw.flush();
bw.close();
}
static class Node {
public int value;
public int index;
Node(int value, int index) {
this.value = value;
this.index = index;
}
}
}
💻 💻 💻