자료구조 / 백준 17298 오큰수

문제 접근

수열을 비교하면서 현재 원소가 이전 원소보다 클 때까지 수열의 index를 스택에 push

그러고 해당 인덱스에 해당하는 원소들을 현재 원소로 바꿈

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;


public class G17298 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        Stack<Integer> stack = new Stack<>();

        int N = Integer.parseInt(br.readLine());

        int[] A = new int[N];

        String[] split = br.readLine().split(" ");

        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(split[i]);
        }

        for (int i = 0; i < N; i++) {
            while (!stack.isEmpty() && A[stack.peek()] < A[i]) {
                A[stack.pop()] = A[i];
            }
            stack.push(i);
        }

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

        for (int i = 0; i < N; i++) {
            sb.append(A[i]).append(" ");
        }

        System.out.println(sb);

    }
}

 

스택이 비어있지 않고 현재 원소가 이전 원소보다 큰 경우에 스택의 원소를 pop하고 값을 현재 원소로 바꿈

 

스택에 남아있는 인덱스들의 원소 값을 -1로 바꿈