[백준/JAVA] 2493 - 탑

[문제 포인트]

가장  최근 의 자기 보다 높이가 큰 탑이 무엇인지 찾는것!! => "스택" 힌트

어떻게 스택의 push와 pop 연산을 사용할지 생각!!!

 

[문제 풀이]

1) 스택이 비어있는 경우(stack.isEmpty())

=> 0을 출력하고, 현재 원소를 스택에 push!!

 

2) 스택이 비어있지 않은 경우(!stack.isEmpty())

2-1) 스택의 top 원소 > 현재 원소 => 스택의 top 원소의 인덱스를 출력하고, 현재 원소를 스택에 push!!

2-2) 스택의 top 원소 < 현재 원소 => 스택에서 pop!! => 다시 1)인지 2)인지로.. 반복...

 

import java.io.*;
import java.util.*;
 
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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        Stack<int[]> stack = new Stack<>();
        for(int i = 1; i <= n; i++) {
            int top = Integer.parseInt(st.nextToken());
            while(!stack.isEmpty()) {
                if(stack.peek()[1] >= top) {
                    System.out.print(stack.peek()[0] + " ");
                    break;
                }
                stack.pop();
            }
            if(stack.isEmpty()) {
                System.out.print("0 ");
            }
            stack.push(new int[] {i, top}); 
        }
    }
}

 

[참고]

https://moonsbeen.tistory.com/204

[백준]2493: 탑 - JAVA