백준 - 6198번 옥상 정원 꾸미기

반복문을 두번 쓰면 O(n^2)이라 계속 시간초과가 발생함.

한번만 쓰는 방법이 뭐가 있을까 고민했지만 찾지 못함...

 

 

---

아이디어

: 스택에 저장된 빌딩들의 높이가 다음 빌딩의 높이 height보다 낮다면 스택에서 pop.

height 이후의 다음 빌딩을 볼 수 없기 때문.

높은 애들만 스택에 저장.

스택의 저장되어 있는 애들의 개수를 계속 더한다.

 

 

또 하나 중요한 점은,

sum의 타입은 long으로 선언해야 함.

최악의 경우에 거의 n^2개가 나올 수 있기 때문.

그럼 64억으로 int 타입인 21억을 벗어난다.

 

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

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(
                new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(
                new OutputStreamWriter(System.out));

        int N=Integer.parseInt(br.readLine());
        
        Stack <Integer> stack =new Stack <>();
        long sum=0;
        
        for(int i=0;i<N;i++){
            int height=Integer.parseInt(br.readLine());
            
            while(!stack.isEmpty()){
                if(stack.peek()<=height)
                    stack.pop();
                else
                    break;
            }
            sum+=stack.size();
            stack.push(height);
        }
        
        bw.write(Long.toString(sum));
        bw.flush();
        bw.close();
    }
}