https://www.acmicpc.net/problem/17298
1. 문제 요약
크기가 N인 수열의 각 원소의 오큰수를 구한다.
오큰수는 해당 원소보다 오른쪽에 있으면서 더 큰 값을 갖는 수 중 가장 왼쪽에 있는 수를 의미한다.
이러한 수가 없다면 오큰수는 -1의 값을 갖는다.
수열의 크기 N은 최대 100만, 각 원소의 값은 최대 100만이다.
2. 문제 접근
각 원소의 값은 최대 100만인데, 따로 연산을 수행하지 않으므로 int범위를 넘어서지는 않는다. 따라서 int형을 사용하면 된다.
입력의 크기가 최대 100만이기 때문에 시간복잡도는 까지 가능하다.
오큰수는 결국 각 원소에 대해 오른쪽을 훑다가 가장 먼저 만나는 더 큰 값이라고 생각할 수 있다.
그렇다고 완전탐색으로 훑는다면 이 되기 때문에 시간초과가 날 것이다.
백준 단계별로 풀어보기에 스택 2 단계로 되어있지만, 우선순위 큐(PriorityQueue)를 사용하는 해결 방법이 먼저 떠올라서 해결하였고, 이후 스택(Stack)을 사용하는 방법으로도 문제를 해결해보았다.
문제를 해결하고보니 우선순위 큐를 사용하는 것과 스택을 사용하는 것은 거의 유사한 방식이었다.
3. 풀이
3.1. 우선순위 큐 사용
기본적인 아이디어는 다음과 같다.
- 가장 낮은 숫자가 먼저 나오도록 하는 우선순위 큐를 설정한다.
- 각 원소를 훑으며 그 값을 우선순위 큐의 첫번째 값과 비교한다.
2.1. 만약 우선순위 큐의 값이 작다면 현재 원소가 그 값의 오큰수이므로 우선순위 큐의 값을 꺼내서 해당 값의 오큰수를 현재 값으로 설정한다.
2.2. 이를 우선순위 큐의 크기가 0이 될 때까지 반복한다. 그 과정에서 우선순위 큐의 값이 같거나 더 크다면 루프를 끝내고 현재 원소를 우선순위 큐에 넣는다.
각 원소를 우선순위 큐에 넣고 빼는 것만 고려하면 되기 때문에 시간복잡도는 이 된다.
다만 우선순위 큐 값의 오큰수를 설정할 때, 해당 값의 오큰수를 설정하기 위해서는 그 값의 인덱스를 알아야 하기 때문에 우선순위 큐에 인덱스도 같이 넣어주어야 한다.
즉, 우선순위 큐는 {원소의 값, 인덱스}의 값을 받아 가장 작은 값부터 출력하도록 설정해야 한다.
또 고려할 점은 오큰수가 없는 경우를 -1로 설정해야 한다는 점이다.
이는 위의 루프에 해당하지 않는 경우이기 때문에 그냥 정답의 기본값을 -1로 해놓고, 루프에서 이 값을 갱신하도록 하면 해결된다.
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 입력 받기
int N = Integer.parseInt(br.readLine());
int[] answer = new int[N]; // 정답을 나타내는 배열
int[] sequence = new int[N]; // 입력 수열을 받는 배열
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
sequence[i] = Integer.parseInt(st.nextToken()); // 입력 수열 받기
answer[i] = -1; // 정답 배열의 기본 값을 -1로 설정
}
// (숫자, 인덱스)를 입력받아 숫자의 오름차순으로 구성되는 우선순위 큐
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] a1, int[] a2) {
return Integer.compare(a1[0], a2[0]);
}
});
// 수열을 훑으며 우선순위 큐 값보다 크다면 오큰수를 설정해주고 현재 값을 또 넣는다.
for (int i = 0; i < N; i++) {
int[] now = {sequence[i], i};
// 우선순위 큐에 값이 있다면 빌 때까지 반복하여 값을 비교한다
while (!pq.isEmpty()) {
int[] head = pq.peek();
// 만약 우선순위 큐의 값이 현재보다 작다면 꺼내서 오큰수를 설정한다.
if (head[0] < now[0]) {
pq.poll();
answer[head[1]] = now[0];
}
// 만약 우선순위 큐의 값이 현재보다 같거나 크다면 루프를 끝낸다.
else break;
}
// 현재 값 넣기
pq.add(now);
}
// 정답 형태 구성 및 출력
for (int i = 0; i < N; i++) {
sb.append(answer[i]+" ");
}
System.out.println(sb);
}
}3.2. 스택 사용
이는 기본적으로 우선순위 큐 방식과 똑같이 작동하는데, 자료구조로 스택을 사용한다는 점만 다르다.
기본적인 아이디어는 다음과 같다.
- 스택을 설정한다.
- 각 원소를 훑으며 그 값을 스택의 Top과 비교한다.
2.1. 만약 스택 Top의 값이 작다면 현재 원소가 Top 값의 오큰수이므로 스택의 값을 꺼내서 해당 값의 오큰수를 현재 값으로 설정한다.
2.2. 이를 스택의 크기가 0이 될 때까지 반복한다. 그 과정에서 스택 Top의 값이 같거나 더 크다면 루프를 끝내고 현재 원소를 스택에 넣는다.
스택을 사용하는게 가능한 이유는 이러한 아이디어를 수행했을 때, 스택의 특정 위치에 있는 값은 그 아래에 있는 값과 같거나 더 작은 값일 수 밖에 없기 때문이다.
즉, 우선순위 큐를 사용하는 것과 유사한 효과를 얻는다.
다만 이는 시간복잡도가 이기 때문에 우선순위 큐를 사용하는 것보다 더 효율적이다.
여기서도 스택에 {원소의 값, 인덱스}로 값을 저장해야 하며, 정답의 기본값을 -1로 설정한다.
이를 구현한 코드는 다음과 같다
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 입력 받기
int N = Integer.parseInt(br.readLine());
int[] answer = new int[N]; // 정답을 나타내는 배열
int[] sequence = new int[N]; // 입력 수열을 받는 배열
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
sequence[i] = Integer.parseInt(st.nextToken()); // 입력 수열 받기
answer[i] = -1; // 정답 배열의 기본 값을 -1로 설정
}
// (숫자, 인덱스)를 입력받는 스택
ArrayDeque<int[]> stack = new ArrayDeque<>();
// 수열의 값을 훑으며 스택의 top보다 크다면 꺼내서 오큰수를 설정한다.
// 스택의 top과 같거나 작을때, 또는 스택이 빈다면 현재값을 넣는다.
// 스택에는 (숫자, 인덱스)의 형태로 값이 저장된다.
for (int i = 0; i < N; i++) {
int[] now = {sequence[i], i};
while (!stack.isEmpty()) {
int[] top = stack.peek();
// 만약 스택의 top이 현재 값보다 작다면 꺼내서 오큰수를 설정한다.
if (top[0] < now[0]) {
stack.pop();
answer[top[1]] = now[0];
}
// 만약 스택의 top이 현재 값보다 같거나 크다면 루프를 끝낸다.
else break;
}
stack.push(now);
}
// 정답 형태 구성 및 출력
for (int i = 0; i < N; i++) {
sb.append(answer[i]+" ");
}
System.out.println(sb);
}
}4. 회고
ArrayDeque를 스택으로 사용할 때, top연산을 어떻게 해야할 지 잘 몰랐는데, 알고보니 peek 메서드를 사용하면 된다.
ArrayDeque의 push는 addFirst와 같고, pop은 removeFirst와 같으며, peek은 peekFirst와 같다.
