백준 2493번: 탑[JAVA]

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

2493번: 탑

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        Stack<int[]> stack = new Stack<>();
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) { // 탑은 0번부터가 아닌 1번부터 시작
            int top = Integer.parseInt(st.nextToken()); // 현재 확인중인 탑
            while (!stack.isEmpty()) {
                if (stack.peek()[1] >= top) {
                    bw.write(stack.peek()[0] + " ");
                    break;
                }
                stack.pop();
            }
            if (stack.isEmpty()) {
                bw.write("0 ");
            }
            stack.push(new int[]{i, top});
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

[설명]

제일 왼쪽 탑부터 스택에 담긴 값들과 비교해가면 로직을 반복한다.

스택에는 높이가 작은 순서부터 큰순으로 오름차순으로값이 담기게 된다.

 

높은 6탑은 첫번째 탑이기 때문에 비교할 스택들이 없어 0을 bw.write 한 후 {탑의 위치, 탑의 높이}를 스택에 담는다.

 

높이 9탑은 스택에 담긴 6보다 높이가 높다. 그 뜻은 앞으로 확인할 탑들은 모두 높이 9 탑 때문에 스택에 담겼던 높이 6 탑을 만날 수 없다. 그러므로 높이 6 스택은 pop해준다. 높이 9 탑을 스택에 담는다.

 

높이 5탑과 스택에 담긴 높이9 탑과 비교해준다. 높이9 탑에 신호가 닿기 때문에 높이9의 위치를 출력해준 후 스택에 높이 5 스택을 담아준다.

 

높이 7탑과 스택에 담긴값과 비교해준다. 스택의 가장 위의 값인 높이 5와 비교를 해본다. 스택에 담겼던 스택 5탑은 현재 확인중인 높이 7탑 때문에 앞으로 모든신호를 못받게된다. 그러므로 스택에서 pop 해준다. 그 다음 스택에 담긴 값 높이 9랑 비교 하면 신호가 9에 닿는다. 9의 위치를 출력후 높이7 탑을 스택에 담는다.

 

높이 4탑과 스택에 담긴 값을 비교해본다. 스택의 top에 있는값 높이 7인탑과 비교해보니 바로 신호가 닿는다. 높이 7탑의 위치를 출력해준다.