[백준/Java] 2493번 탑

-Code

import java.io.*;
import java.util.*;

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] heights = new int[cnt];
        for (int i = 0; i < cnt; i++) {
           heights[i] = Integer.parseInt(st.nextToken());
        }
        // 이전 상태와 비교하기 위해 단조 큐 선언
        Deque<Integer> deq = new ArrayDeque<>();
        // 결과 계산
        int[] answer = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            // 단조 큐가 비어있지 않고 현재 값보다 작은 값 다 제거
            while (!deq.isEmpty() &&
                    heights[deq.peekLast()] < heights[i]) {
                deq.pollLast();
            }
            // 내 이전에 나보다 높은 높이가 존재하면 입력
            if (!deq.isEmpty()) {
                answer[i] = deq.peekLast() + 1;
            }
            // 현재 높이 저장
            deq.addLast(i);
        }
        // 출력
        StringBuilder sb = new StringBuilder();
        for (int n : answer) {
            sb.append(n).append(" ");
        }
        System.out.println(sb);
        br.close();
    }
}

어제 단조큐 문제를 보고 다른 문제도 풀고 싶어서 시도해 봤으나 풀지 못해서 힌트만 보고 오늘 처음부터 다시 구현해 봤습니다.

어제 푼 프로그래머스의 문제와 좀 다른 문제라 접근이나 로직을 처음에 이상하게 짜게 되어서 틀렸습니다. 그래서 이 부분을 단조큐 내의 값이 클 때까지 빼고 계산해 보라는 힌트로 해결했습니다.