[BOJ] 17298: 오큰수 (JAVA)

문제

https://www.acmicpc.net/problem/17298

 

여담

탑 문제랑 옥상 정원 문제랑 거의 비슷한 유형이다. 그래서 이전에 풀었던 방식으로 쉽게 풀 수 있었다. 그런데 이미 관련 문제들을 풀어보고 문제 유형을 알기 때문에 바로 풀 수 있었다고 생각한다. 나중에 유형에 대한 힌트 없이 다시 풀어볼 필요가 있겠다!

 

풀이

오큰수는 현재 원소의 오른쪽에 있으면서 현재 원소보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 즉, 현재 원소보다 크고 오른쪽에 위치하는 수 중에서 제일 첫 번째로 등장하는 수를 뜻한다.

 

따라서 가장 오른쪽에 위치하는 원소부터 스택에 넣어서 검사하는 방식으로 수행하면 시간 초과없이 풀 수 있다. 아래의 과정을 각 원소마다 반복해서 수행하면 된다. 

1. 스택이 비어있는 경우
   • -1을 기록하고 현재 수를 스택에 push하기
2. 스택이 비어있지 않는 경우
   • 스택에 peek한 원소 > 현재 원소
     • peek한 원소를 기록하고 현재 원소를 스택에 push하기
     • 현재 원소의 탐색을 종료하기
   • 스택에 peek한 원소 ≤ 현재 원소
     • peek한 원소를 pop하기

 

예시

수열이 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);
    }
}

---