[BOJ] 2493번 탑 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb;
    static Stack<Tower> stack = new Stack<>();
    static int N;

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

        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            Tower now = new Tower(i + 1, Integer.parseInt(st.nextToken()));

            while (!stack.isEmpty()) {
                Tower top = stack.peek();
                if (top.height >= now.height) {
                    sb.append(top.idx).append(" ");
                    break;
                }
                stack.pop();
            }

            if (stack.isEmpty()) {
                sb.append(0).append(" ");
            }

            stack.push(now);
        }
        System.out.println(sb);
    }

    static class Tower {
        int idx;
        int height;

        public Tower(int idx, int height) {
            this.idx = idx;
            this.height = height;
        }
    }
}

📄 해설

접근

• 스택을 사용하고, 탑의 높이와 번호 정보를 저장할 Tower 클래스를 사용하는 문제
• 한 개의 탑이 한 개의 신호를 수신할 수 있다는 부분에서 스택으로 접근했다.

과정

• Tower 타입의 스택을 선언하고, 입력 받은 숫자들에 대해 아래 과정을 반복한다.
• 입력 받은 높이와 인덱스 번호를 담는 Tower 객체 하나를 만든다.
• 스택이 빌때까지 반복문을 실행하고, 아래 과정을 수행한다.
  • 스택의 탑(Top)의 높이가 현재 새로운 탑(Tower)의 높이보다 크거나 같은 경우, 스택 탑의 번호를 출력한다.
  • 스택에 Pop 연산을 수행한다.
• 스택이 빈 경우, 0 을 출력한다.
• 위 과정이 끝나면 현재 탑(Tower) 를 스택에 넣는다.