[백준] 2493 탑 - Data Structure / Java

• 문제 링크

2493번: 탑

 

• 풀이 과정

각각의 탑의 번호와 높이를 저장할 Tower 객체를 정의하고 Stack 자료구조의 제네릭으로 지정한다.

 

입력받은 탑의 정보를 스택에 삽입하면서,

peek() 하여 반환한 스택 최상단 요소의 height 값, 즉 왼쪽 탑의 높이를 현재 탑과 비교하여

만약 왼쪽 탑이 높이가 낮다면 레이저 신호를 수신할 수 없으므로 pop() 하고,

높이가 같거나 높다면 해당 왼쪽 탑의 번호를 정답으로써 출력한다.

 

만약 스택이 비어있을 시, 현재 탑으로부터 레이저 신호를 수신할 수 있는 탑이 존재하지 않으므로 0 을 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        Stack<Tower> stk = new Stack<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            int height = Integer.parseInt(st.nextToken());
            while (!stk.empty()) {
                if (stk.peek().height >= height) {
                    bw.write(stk.peek().num + " ");
                    break;
                }

                stk.pop();
            }
            if (stk.empty())
                bw.write("0 ");

            stk.push(new Tower(i, height));
        }

        bw.flush();
    }

    private static class Tower {
        int num, height;

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

}