[BOJ] 6198. 옥상 정원 꾸미기

2493번 탑과 비슷한 스택을 사용하는 문제이다.

문제를 접근할때 현재 빌딩에서 몇개를 볼수있느냐가 아니라 현재 빌딩이 몇개의 빌딩에서 보여지냐 를 기준으로 접근하였다. 그래서 스택을 이용하여 순서대로 입력을 받았다. 그리고 입력을 받은 순간 만일 스택의 top에 있는 빌딩의 높이가 현재 들어온 빌딩보다 높다면 그순간의 스택사이즈를 answer에 추가해주었고, 만일 현재 들어온 빌딩이 더 크다면 스택의 top에 위치한 빌딩을 pop해주었다.

package study4;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
 
public class Main_bj_6198_옥상정원꾸미기 {
    public static void main(String[] args) throws Exception{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        long answer= 0;
        Deque<Long> deque = new LinkedList<>();
 
        int n=Integer.parseInt(br.readLine());
 
        for(int i=0;i<n;i++) {
            long height= Long.parseLong(br.readLine());
 
            while(deque.size()!=0) {
                if(deque.getLast() <= height) {        //새로운 빌딩이 크다면
                    deque.removeLast();
                }else {                                //새로들어오는 빌딩이 앞의 빌딩에서 볼수있다면
                    answer+=deque.size();
                    break;
                }
            }
            
            deque.addLast(height);
        }
        System.out.println(answer);
 
    }
}