문제
https://www.acmicpc.net/problem/17298
여담
탑 문제랑 옥상 정원 문제랑 거의 비슷한 유형이다. 그래서 이전에 풀었던 방식으로 쉽게 풀 수 있었다. 그런데 이미 관련 문제들을 풀어보고 문제 유형을 알기 때문에 바로 풀 수 있었다고 생각한다. 나중에 유형에 대한 힌트 없이 다시 풀어볼 필요가 있겠다!
풀이
오큰수는 현재 원소의 오른쪽에 있으면서 현재 원소보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 즉, 현재 원소보다 크고 오른쪽에 위치하는 수 중에서 제일 첫 번째로 등장하는 수를 뜻한다.
따라서 가장 오른쪽에 위치하는 원소부터 스택에 넣어서 검사하는 방식으로 수행하면 시간 초과없이 풀 수 있다. 아래의 과정을 각 원소마다 반복해서 수행하면 된다.
- 스택이 비어있는 경우
- -1을 기록하고 현재 수를 스택에 push하기
- 스택이 비어있지 않는 경우
- 스택에 peek한 원소 > 현재 원소
- peek한 원소를 기록하고 현재 원소를 스택에 push하기
- 현재 원소의 탐색을 종료하기
- 스택에 peek한 원소 ≤ 현재 원소
- peek한 원소를 pop하기
- 스택에 peek한 원소 > 현재 원소
예시
수열이 9 5 4 8
일 때 풀이 과정은 다음과 같다.
4번 원소
처음에는 스택이 비어있으므로 -1을 기록하고 현재 원소를 스택에 push한다.
3번 원소
스택에서 peek한 원소는 8이고, 현재 원소는 4이다. 즉, peek한 원소가 더 크기 때문에 peek한 원소(=4번)를 기록하고 현재 원소를 push한다.
2번 원소
스택에서 peek한 원소는 8이고, 현재 원소는 5이다. 즉, peek한 원소가 더 크기 때문에 peek한 원소(=4번)를 기록하고 현재 원소를 push한다.
1번 원소
스택에서 peek한 원소는 5이고, 현재 원소는 9이다. 즉, 현재 원소가 더 크기 때문에 peek한 원소(=2번)를 pop한다.
아직 스택이 비어있지 않으므로 다시 비교를 시작한다. 스택에서 peek한 원소는 8이고, 현재 원소는 9이다. 즉, 현재 원소가 더 크기 때문에 peek한 원소(=4번)를 pop한다.
스택이 비었기 때문에 -1을 기록하고 현재 원소를 스택에 push한다.
모든 원소를 검사하면 비교하는 과정을 종료한다.
코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Stack<Integer> stack = new Stack<>();
int[] ans = new int[n]; // 오큰수 기록용
for (int i = n - 1; i >= 0; i--) { // 가장 오른쪽에 위치하는 수부터 탐색
if (stack.isEmpty()) {
ans[i] = -1;
stack.push(arr[i]);
} else {
while (true) {
if (stack.isEmpty()) { // 스택이 비었으면
ans[i] = -1; // -1 기록하고
stack.push(arr[i]); // 스택에 push
break; // 그리고 해당 수에 대한 탐색 종료
}
if (stack.peek().intValue() > arr[i]) { // peek > now 인 경우라면(= 오큰수를 찾은 경우)
ans[i] = stack.peek().intValue(); // 기록하고
stack.push(arr[i]); // 스택에 push
break; // 그리고 해당 수에 대한 탐색 종료
} else { // 그렇지 않다면
stack.pop(); // 스택에서 pop
}
}
}
}
StringBuilder sb = new StringBuilder();
for (int a : ans) {
sb.append(a).append(" ");
}
System.out.println(sb);
}
}
'Algorithm > 자료구조' 카테고리의 다른 글
[BOJ] 5430: AC (JAVA) (1) | 2024.04.10 |
---|---|
[BOJ] 1021: 회전하는 큐 (JAVA) (0) | 2024.04.09 |
[BOJ] 6198: 옥상 정원 꾸미기 (JAVA) (0) | 2024.04.06 |
[BOJ] 2493: 탑 (JAVA) (0) | 2024.04.04 |
[BOJ] 5397: 키로거 (JAVA) (0) | 2024.04.03 |