백준 17298번 오큰수(자바) - 스택

풀이 방법

1. arr[i]의 값이 arr[i-1] 보다 큰 경우가 나올 때까지 i를 stack에 push 한다.

-> 만약 arr[i] 값이 arr[i-1] 보다 작다면 arr[i]의 값이 스택에 있는 모든 인덱스에 저장되어 있는 수보다 작다는 의미이다.

2. arr[i] > arr[i-1] 인 경우 arr[i]보다 큰 수가 나올 때까지  stack에서 인덱스를 하나씩 pop한다.

이 경우 오큰수를 발견한 것이므로 arr[stack.pop()] = arr[i] 해준다.

arr[i] 보다 큰 수가 나왔다면 더이상 pop하지 않고 i를 push 해준다.

3. 인덱스 맨 끝까지 탐색을 마쳤다면 스택에 있는 값을 하나씩 pop 해주며 해당 인덱스에 -1 값을 넣어준다.

(이 경우 자신보다 큰 오큰수를 발견하지 못한 것이다.)

 

*시간 초과

: 그냥 System.out.print를 통해 출력했을 때 시간초과가 났다.

Stringbuilder 사용하자

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                int idx = stack.pop();
                arr[idx] = arr[i];
            }
            stack.add(i);
        }

        while (!stack.isEmpty()) {
            arr[stack.pop()] = -1;
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            sb.append(arr[i]).append(' ');
        }

        System.out.println(sb);
    }
}