[백준 6198 JAVA] 옥상 정원 꾸미기

 

Stack을 활용하는 문제

 

한 방향으로만 건물을 볼수있다 => 이미 앞에있는 건물들은 신경안써도 된다.

이미 stack안에 존재하는 건물들이 새로 들어온 건물을 볼수 있냐 없냐에만 신경쓰면됨

=> 이미 stack에있는 건물보다 큰 건물이 들어왔을때는 stack에서 제거 : stack에 있는 건물들은 이 건물을 볼 수 없기 때문에

=> stack에 있는 건물보다 작은 건물이 들어왔을때 : stack에 push

이 로직으로 진행한다면 stack안에는 새로 들어오는 건물을 볼 수 있는 건물만 남게 된다.

 

새로 들어온 건물을 몇개가 볼수있느냐? 로 이해하면 금방 풀리는 문제

 

단 건물의 크기가 10억까지 존재함으로 long타입을 써야 overflow가 나지 않는다.

 

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Stack<Integer> st = new Stack<>();
        long answer = 0;
        for (int i = 0; i < N; i++) {
            int building = Integer.parseInt(br.readLine());
            // stack 이 비었을때는 Pass
            if (st.isEmpty()) {
                st.add(building);
                continue;
            }
            //stack이 비지않았고 stack의 꼭대기에 있는 building이 새로들어오는 building의 크기보다 작거나같을때 stack에서 제거
            //새로들어오는애보다 낮은 building은 어쩌피 들어오는 building들을 못봄
            while(!st.isEmpty() && st.peek()<=building){
                    st.pop();
            }
            //stack에 있는 애들은 새로 들어오는 building을 볼수있는 building들
            answer +=st.size();
            st.add(building);
        }
        System.out.println(answer);
    }
}