44 삐약 : 백준 6198| 옥상정원 꾸미기 [바킹독 문제 풀이|스택|JAVA]

https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

 

package BKD_0x5_Stack;

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

public class BOJ_6198 {
    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 result=0;

        for(int i=0;i<n;i++){
            int input_num = Integer.parseInt(br.readLine());
            while (!st.isEmpty() && st.peek( )<= input_num) st.pop();

            st.push(input_num);
            result += st.size()-1;
        }

        System.out.println(result);
        br.close();


    }
}

 

 

 

👀 주목주목 👀

 

입력 조건
첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)

 

N의 값이 주어진 조건에서의 최대값일 때 모든 건물이 내림차순 일 경우의 결과값은

 

79999+79998 ... +1 = 80000*80001/2 => 32억이 넘어 int로 표기할 수 있는 범위를 벗어나게 된다.

 

이를 해결하기 위해서는 결과값을 저장하는 변수를 long으로 선언하여 코드를 구현하도록 해야 한다.

 

이거때매 틀렸었음

 

 

 

stack.size()-1이 의미하는것 

• 현재 들어오는 높이의 건물이 보이는 좌측 건물의 개수
• == input 건물을 관리할 수 있는 좌측 건물의 개수

 

 

 

stack에 남아있는 값의 의미

• 우측에 관리가능한 아파트가 존재함을 의미