[백준] 2493번 Java (Stack)

https://www.acmicpc.net/problem/2493

💡문제

풀이

접근법:

탑의 높이가 이전의 모든 탑보다 높은 경우 :
수신을 받을 수 없음. -> 스택(현재까지 확인한 탑)에서 제거한다.

• while 조건 : 현재 탑 i가 왼쪽에 있는 탑들보다 더 높을 때, 왼쪽에 있는 낮은 탑들은 더 이상 현재 탑과 이후의 탑들로부터 신호를 수신할 가능성이 없으므로 제거.
• 스택의 맨 위 요소를 계속 제거(pop()).
• 이 과정은 현재 탑 i보다 더 큰 탑이 나올 때까지, 이전의 작은 탑들을 제거하면서 수행.

	// 스택이 비지 않으며,
    // 현재 탑의 높이 > 스택에 저장된 탑(맨 위)의 높이 = 해당 탑은 수신 X
	while(!stack.isEmpty() && height[i]>height[stack.peek()]){
 	  stack.pop();
	}

• 따라서 만약 스택이 비어있다면 = 수신한 탑이 없음
• 스택에 남은 게 있다면 = 수신한 탑이 있음

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());    // 탑의 수
        
        int [] height = new int[n]; // 탑의 높이 배열
        int [] index = new int[n];  // 신호를 수신한 탑의 인덱스
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            height[i] =(Integer.parseInt(st.nextToken()));
        }

        Deque<Integer> stack = new ArrayDeque<>();  // 현재 탑의 인덱스
        
        for (int i = 0; i < n; i++) {
            // 탑이 이전 모든 탑보다 커서 수신을 받을 수 없다면 제거
            while(!stack.isEmpty() && height[i]>height[stack.peek()]){
                stack.pop();
            }
            
            // 스택이 비어있지 않다면 수신한 탑이 있음.
            if(!stack.isEmpty()){
                index[i] = stack.peek() + 1;
            } else{ // 비어있다면 수신한 탑이 없음.
                index[i] = 0;
            }
            
            // 스택에 현재 탑의 인덱스 추가
            stack.push(i);
        }
        
        // 출력
        StringBuilder sb = new StringBuilder();
        for(int i : index){
            sb.append(i).append(" ");
        }
        System.out.println(sb);
    }
}