[백준] 2493번 : 탑

탑

---

풀이방법

참고 블로그 https://coding-factory.tistory.com/601

1. 스택이 비어있다면 0을 출력하고, 현재 탑을 스택에 push한다.

2. 스택이 비어있지않다면

   2-1. 스택에 peek한 탑의 높이가 현재 탑의 높이보다 높다면, peek한 탑의 번호를 출력하고, 현재 탑을 스택에 push한다.

   2-2. 스택에 peek한 탑의 높이가 현재 탑의 높이보다 낮다면, peek한 탑을 pop하고 2번으로 다시 돌아간다.

배운 점

스택에 높이와 해당 인덱스를 가지는 클래스를 사용해 2개의 정보를 같이 저장.

• 알고 있었던 정보지만, 막상 사용하려고 하면 이런 기본적인게 생각이 잘 안난다..
  많이 공부해야겠다ㅠㅠ

---

코드

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

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

class Main {
    static Stack<Top> stack = new Stack<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder();

        for(int i=1;i<=n;i++){
            int height = Integer.parseInt(st.nextToken());

            if(stack.empty()){
                sb.append(0 + " ");
                stack.push(new Top(i,height));
            } else{
                while(true){
                    if(stack.empty()){
                        sb.append(0 + " ");
                        stack.push(new Top(i,height));
                        break;
                    }
                    Top top = stack.peek();
                    if (top.height > height) {
                        sb.append(top.num + " ");
                        stack.push(new Top(i, height));
                        break;
                    } else {
                        stack.pop();
                    }
                }
            }
        }

        System.out.println(sb);
    }
}