[백준] 11298

 

스택을 인덱스로 활용할 발상의 전환이 필요하다.

 

배열을 순회하면서 현재 원소가 이전의 원소보다 작을 때 까지 배열의 index를 stack에 push 한다.

그리고 만약 현재 원소가 스택의 top 원소를 인덱스로 하는 수열의 원소보다 크게 될 경우 stack의 원소를 pop하면서 해당 인덱스에 해당하는 원소들을 현재 원소로 바꿔주는 것이다.

 

3 5 2 7

 

Stack

[0]    [3,5,2,7]

 

3<5

스택이 빌때까지 반복

arr[stack.pop()]) = arr[i]

=>  arr[0] = arr[1]

[5,5,2,7]

stack  empty상태

 

5>2

Stack       

[1,2] 

 

2<7

스택이 빌때까지 반복

arr[stack.pop()] = arr[i]

=> arr[2] = arr[3]

[5,5,7,7]

Stack

[1]

 

=> arr[1] = arr[3]

[5,7,7,7]

Stack  empty상태

 

반복문 종료시

Stack

[3]

 

마지막 원소는 비교할게 없음으로 -1

arr[stack.pop()] = -1

arr[3] = -1

 

[5,7,7,-1]

 

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

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

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        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;
        }
        
        for (int i=0; i<N; i++) {
            sb.append(arr[i]).append(" ");
        }

        System.out.println(sb);
    }
}