https://www.acmicpc.net/problem/11003
1. 문제 설명
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)
2. 풀이
Deque를 이용해서 풀 수 있다.
c++의 경우 세그먼트 트리 , 우선순위 큐를 이용해서 풀 수 있는데, Java의 경우는 불가능하다... (시간 초과 남)
아마, Java의 경우 입출력이 시간이 오래 걸려서 그러는 듯하다.
deque를 이용해서 정렬을 하여 풀 수 있다.
deque에는 인덱스 값과 숫자 값을 저장한다.
정렬을 하는 법은 간단한데, deque 뒤에서부터 deque보다 큰 값들은 모두 삭제해버리고 현재 값을 저장하면 된다.
Ai-L+1 ~ Ai 의 최솟값을 구하는 문제이기 때문에 deque에 이미 들어있는 값들은 현재 인덱스보다 작은 인덱스이면서 현재 값 보다 크기 때문에 최솟값 Di로 사용되지 않는다.
예를 들어 현재 deque에 숫자 값들이 9 10 11이 저장되어 있을 때 1이 들어오게 되면 9 10 11은 현재 인덱스 이후로 절대 Di로 사용되지 않기에 없애버려도 된다.
현재 값은 무조건 저장하는 이유는 그 뒤에 값들이 얼마가 나올지 모르기 때문이다. 예를 들어 현재 deque에 1 2 3 이 저장되어 있을 때 10이 들어왔다면 현재 인덱스의 최솟값은 아니지만, 뒤에 계속해서 10보다 큰 값들만 들어오게 된다면 언젠가는 10이 Di로 사용될 것이다.
이런 식으로, 현재 값보다 큰 값들을 제거해나가면 저절로 정렬이 될 것이다..!
주의해야 될 점은, 구간이 정해져 있기 때문에 구간을 벗어나는 값은 제거해 줘야 된다는 것이다.
구간을 벗어나는 값을 제거할 때 deque에 첫 번째 원소만 확인했는데, 이것은 우리가 이미 정렬을 했기 때문에 첫 번째 원소만 확인해도 된다.
정렬을 했기 때문에 첫번째 원소는 제일 처음에 deque에 들어온 값이며 제일 작은 값이다. 따라서 첫 번째 원소만 확인해도 된다!
처음에 많이 틀렸는데 deque empty 조건을 달지 않아서 NullPointer 에러가 났었다.
혹시 NullPointer가 발생하시는 분이 계시다면 deque가 비어있는데 deque 원소에 접근하지 않는지 확인해보시는 것이 좋다.
*로직
- Deque에 첫번째 값이 구간을 벗어나는지 확인. 벗어난다면 제거
- Deque에 마지막부터 현재 값보다 큰 값들 제거
- Deque에 첫번째 원소 출력
3. 코드
import java.awt.*;
import java.io.*;
import java.util.*;
public class Main {
public static Deque<Point> deque = new LinkedList<>();
public static int N, L;
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());
deque.addFirst(new Point(1000000001,-1));
st = new StringTokenizer(br.readLine());
for (int x = 0; x < N; x++) {
int now = Integer.parseInt(st.nextToken());
// 앞에 범위 벗어나는 것 버림
if (!deque.isEmpty() && deque.peekFirst().idx <= x - L) {
deque.pollFirst();
}
// 뒤에서부터 큰거 버림
while (!deque.isEmpty() && deque.peekLast().num >= now) {
deque.pollLast();
}
deque.addLast(new Point(now, x));
bw.write(String.valueOf(deque.peekFirst().num) + " ");
}
bw.flush();
}
public static class Point{
int num, idx;
Point(int num, int idx) {
this.num = num;
this.idx = idx;
}
}
}
'알고리즘' 카테고리의 다른 글
[JAVA]백준 1072번: 게임 (1) | 2021.07.23 |
---|---|
[JAVA]백준 1837번: 암호제작 (0) | 2021.07.23 |
[JAVA]백준 2805번: 나무 자르기 (0) | 2021.07.21 |
[JAVA]백준 2003번: 수들의 합 (0) | 2021.07.20 |
[JAVA]백준 1339번: 단어 수학 (0) | 2021.07.20 |