[자료구조] Stack 문제 풀이

백준 2493

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

class Top { // 탑에 대한 정보
    int num; // 탑의 번호
    int height; // 탑의 높이
 
    Top(int num, int height) {
        this.num = num;
        this.height = height;
    }
}
 
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;
        int N = Integer.parseInt(br.readLine());
 
        Stack<Top> stack = new Stack<>();
        StringBuilder answer = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            int height = Integer.parseInt(st.nextToken());
 
                while (true) { 
                    if (stack.isEmpty()) { // 스택이 비어있다면, 0을 출력하고 탑을 push한다.
                        answer.append("0 ");
                        stack.push(new Top(i, height));
                        break;
                    }
 
                    Top top = stack.peek();
 
                    if (top.height > height) { // peek한 탑의 높이가 현재 탑의 높이보다 높다면,
                        answer.append(top.num + " "); // peek한 탑의 번호를 출력하고,
                        stack.push(new Top(i, height)); // 현재 탑을 스택에 push한다.
                        break;
                    } else { // peek한 탑의 높이가 현재 탑의 높이보다 낮다면,
                        stack.pop(); // 스택에서 pop하고 다시 반복문을 돌린다.
                    }
                }
            
        }
 
        bw.write(answer.toString() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

얻어갈 점:

• 처음에는 배열에 탑들의 정보를 미리 넣고, 맨 끝 인덱스부터 앞과 비교하여 신호를 받을 수 있는 탑을 찾으려 했으나 그렇게 하면 시간 초과가 날 수 밖에 없음(시간복잡도에 의해)
• Stack을 사용할 수 있었던 이유? 입력된 변수가 가장 가까운 탑과 비교를 통해 꺼낼지, 말지를 결정하기 때문에 사용했음
• 탑의 인덱스와 높이를 어떻게 저장할지 고민 했었는데, 자바 언어의 특성인 객체를 사용하여 깔끔하게 정리할 수 있음.