백준 - 6198 옥상정원꾸미기

 

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

6198번: 옥상 정원 꾸미기

 

 

스택에 아이템을 한 개씩 push하면서 스택의 top()과 비교한다.

push 한 아이템의 높이가 스택의 top() 보다 작다면 스택의 모든 원소들은 그 아이템을 볼 수 있다는 뜻이다.

그러므로 답에 스택의 크기만큼 더해준다.

아이템의 크기가 스택의 값보다 크거나 같다면 스택의 top() 더이상 아이템 오른쪽에 있는 것들을 보지 못하므로 pop 시켜주고 이를 모든 아이템에 대해서 반복하면 된다.

 

시간복잡도는 O(N)이다.

 

 

 

 

import java.io.*;
import java.util.*;
public class Main {
	static class MyScanner {
		StringTokenizer st;
		BufferedReader bf;

		MyScanner() {
			bf = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}

			return st.nextToken();
		}

		int nextInt() {

			return Integer.parseInt(next());
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner();
		int N = sc.nextInt();
		int bld[] = new int[N];
		for(int i =0 ;i < N;i++) {
			bld[i] = sc.nextInt();
		}
		long answer = 0;
		Stack <Integer> stack = new Stack<>();
		stack.add(bld[0]);
		
		for(int i =1 ;i < N ;i++) {

			while(!stack.isEmpty() && stack.peek()<=bld[i]) {
				stack.pop();
			}
			answer+=stack.size();
			stack.add(bld[i]);
		}
		System.out.println(answer);
		
		
		
		
	}

}