백준 17298 자바 - 오큰수

문제

---

 

 

 

문제해결

---

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

public class B17298 {
    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]){
                arr[stack.pop()] = arr[i];
            }

            stack.push(i);
        }

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

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

- 이중 포문을 사용하여 하나하나 체크하는 방법도 있지만 시간 초과가 난다

해결 방법:

- 수열을 하나씩 돌면서 오른쪽 숫자들 중 자기보다 큰 숫자가 나타날 때까지 해당 인덱스를 스텍에 저장시켜 놓는다

- 자기보다 큰 숫자가 나타날 경우 스텍에 있는 모든 인덱스 위치를 전부 해당 숫자로 변경한다

- 수열을 다 돌고 나서도 스텍에 남아있는 인덱스가 있다면 오큰수가 없는 숫자이므로 -1로 변경한다

 

출처: https://st-lab.tistory.com/196