백준 - 11003. 최솟값 찾기
이런저런 방법으로 접근한 문제라서 정리하고자 한다.
11003. 최솟값 찾기
https://www.acmicpc.net/problem/11003
문제
입출력
설명
구간을 이동하면서 구간 내의 최솟값을 출력하면 되는 문제이다.
문제 자체는 매우 짧고 간단하다.
접근
우선 시간제한이 매우 짧고 N의 값이 최대 500만이므로 시간복잡도 O(N)을 떠올렸다.
즉, 값을 입력받을 때 바로 출력해야 한다고 생각했다.
알고리즘은 전체 N개의 값이 주어지고 구간을 이동하며 L개의 값 중 최솟값을 출력하는 문제이므로 슬라이딩 윈도우가 떠올랐다. 하지만 이 알고리즘을 활용하기엔 큰 문제가 있다.
바로 최솟값을 다시 찾을 때 L만큼 반복문을 돌아야 한다는 것이다.
이 문제점을 해결하는 것이 이 문제의 목적이라는 것을 질문 게시판에서 읽었다.
정말인지는 알 수 없지만 풀이 조건을 생각했을 때 맞다고 생각한다.
풀이를 위해선 Deque를 활용해야 하며 방법은 아래와 같다.
한 방향은 아래와 같이 숫자를 비교한다.
값을 새로 받을 때마다 이 과정을 반복하므로 Deque는 계속 정렬된 상태이다.
반대 방향은 index 번호를 확인한다.
L 범위 내의 숫자만 사용할 수 있기 때문에 이를 확인하고 pop 한다.
이 과정을 처음부터 끝까지 반복하면 된다.
풀이 코드
Deque를 떠올리지 못하고 여러 방법으로 접근하다가 성공했다.
1. 실패 - 정말 생각 없이 푼 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
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());
st = new StringTokenizer(br.readLine());
int count = 1;
int min = Integer.MAX_VALUE;
int[] numbers = new int[N];
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
numbers[i] = Integer.parseInt(st.nextToken());
if (count == L) {
min = Integer.MAX_VALUE;
for (int j = i - L + 1; j <= i; j++) {
if (numbers[j] <= min) {
min = numbers[j];
count = i - j + 1;
}
}
sb.append(min).append(' ');
continue;
}
if (numbers[i] <= min) {
min = numbers[i];
count = 1;
} else {
count++;
}
sb.append(min).append(' ');
}
System.out.print(sb);
}
}
2. 실패 - PriorityQueue를 활용해 푼 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
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());
st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
PriorityQueue<Index> pq = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
pq.add(new Index(Integer.parseInt(st.nextToken()), i));
while (i - pq.peek().index >= L)
pq.poll();
sb.append(pq.peek().number).append(' ');
}
System.out.print(sb);
}
}
class Index implements Comparable<Index> {
int number;
int index;
Index(int number, int index) {
this.number = number;
this.index = index;
}
@Override
public int compareTo(Index o) {
return number - o.number;
}
}
3. 성공 - Deque을 활용해 푼 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
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());
st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
Deque<Index> deque = new ArrayDeque<>();
for (int i = 0; i < N; i++) {
Index current = new Index(Integer.parseInt(st.nextToken()), i);
while (!deque.isEmpty() && deque.peekLast().number > current.number) {
deque.pollLast();
}
deque.addLast(current);
if (i - deque.peekFirst().index >= L) {
deque.pollFirst();
}
sb.append(deque.peekFirst().number).append(' ');
}
System.out.print(sb);
}
}
class Index {
int number;
int index;
Index(int number, int index) {
this.number = number;
this.index = index;
}
}
후기
PriorityQueue를 활용한 코드에서 성공할 것이라고 생각했는데 틀려서 당황했다. 꽤나 제한이 빡빡해서 고생했다.
.. 지금 후기를 작성하며 생각해 보니 난이도가 Platinum 5인데 너무 안일했던 것 같다.