[백준 6198] 옥상 정원 꾸미기 (C++, Java)

문제 링크: https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

 

1. 주의할 점

- N^2으로 풀지 않도록 한다 -> TLE 발생

- Stack을 사용하여 풀도록 한다

 

2. 구현

- 모든 수들을 배열 Arr[]에 입력받으며, 가장 높은 빌딩의 높이+1을 Maxi 변수에 넣는다(가장 오른쪽에 위치한 건물의 오른쪽에 가상의 Maxi 높이만큼의 건물이 있다고 가정하고 풀기 위해 사용한다)

- 건물 배열은 1~N에 담았기 때문에 N+1번째 빌딩의 높이는 Maxi라고 가정하고 Stack에 넣는다

- N번 건물부터 1번 건물까지 역순으로 확인하며 현재 건물과 현재 Stack의 Top에 담겨있는 원소의 높이와 비교한다

- 만약 Stack의 Top의 높이가 더 크다면(현재 빌딩보다 오른쪽에 위치하며, 작지 않은 높이의 아파트에 도달한 경우) 해당 빌딩의 Idx - 현재 빌딩의 Idx -1만큼 결과에 더해준 후, Stack에 현재 빌딩에 대한 정보를 담는다

- 만약 Stack의 Top의 높이가 더 작다면 S.pop()을 통해 다음 빌딩과 비교할 수 있도록 한다

 

[C++]

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
struct info {
	int idx, height;
};
info tmp;
int arr[80001];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int maxi = 0, num;
	long long result = 0;
	cin >> num;
	for (int i = 1; i <= num; i++) {
		cin >> arr[i];
		maxi = max(maxi, arr[i]);
	}
	stack<info> s;
	tmp.height = maxi + 1;
	tmp.idx = num + 1;
	s.push(tmp);
	for (int i = num; i > 0; i--) {
		int ch = arr[i];
		while (!s.empty()) {
			int sh = s.top().height;
			int si = s.top().idx;
			if (sh < ch)		//오른쪽에 더 높은 빌딩이 없는 경우
				s.pop();
			else {		//오른쪽에 더 높은 빌딩이 있는 경우
				result += (si - i - 1);
				tmp.height = ch;
				tmp.idx = i;
				s.push(tmp);
				break;
			}
		}
	}
	cout << result;
	return 0;
}

 

[Java]

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

public class Main {
	
	static class Info{
		int idx,height;
		public Info(int idx, int height) {
			this.idx = idx;
			this.height = height;
		}
	}
	
	static int n;
	static int arr[];
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine().trim();
		StringTokenizer st = new StringTokenizer(str);
		n = Integer.parseInt(st.nextToken());
		arr = new int[n+2];
		int maxi = 0;
		for(int i=1;i<=n;i++) {
			str = br.readLine().trim();
			st= new StringTokenizer(str);
			arr[i]=Integer.parseInt(st.nextToken());
			maxi = Math.max(maxi, arr[i]);
		}
		long cnt=0;
		Stack<Info> s = new Stack<>();
		s.add(new Info(n+1,maxi+1));
		
		for(int i=n;i>0;i--) {
			int ch = arr[i];		//현재 건물의 높이
			while(!s.isEmpty()) {
				int hh = s.peek().height;
				if(hh>=ch) {
					cnt+=(s.peek().idx-i-1);
					s.add(new Info(i,ch));
					break;
				}
				else 
					s.pop();
			}
		}
		System.out.println(cnt);
	}
}