[BOJ] 백준 6198번: 옥상 정원 꾸미기_자바(JAVA)

1. 문제

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

6198번: 옥상 정원 꾸미기

 이 문제를 풀기 바로 전에 풀었던 탑 문제와 유사하다.

https://delay100.tistory.com/108

[BOJ] 백준 2493번: 탑_자바(JAVA)

---

2. 접근 및 해결

2-1) 접근

// 입력
6
10
3
7
4
12
2

stack = []

10일 때, 0

stack = [10] 

3일 때, 1 (3을 볼 수 있는 것은 stack의 10뿐이기 때문에 stack.size=1)

stack = [10, 3]

7일 때, 1 (7을 볼 수 있는 것은 stack의 10뿐이기 때문에 3을 pop하고 stack.size=1)

stack = [10, 7]

4일 때, 2 (4를 볼 수 있는 것은 stack의 10, 7이기 때문에 stack.size=2)

stack = [10, 7, 4]

12일 때, 0 (12를 볼 수 있는 것은 stack에서 아무것도 없기 때문에 pop을 3번(4, 7, 10 순서로)하고 stack.size=1)

stack = [12]

2일 때, 1 (2를 볼 수 있는 것은 stack에서 12이므로 stack.size=1)

stack = [12, 2]

 따라서, 1+1+2+0+1 = 5가 됩니다.

 

2-2) 해결

 

*시간초과 시 점검 사항

for 문을 이용하면 시간초과가 발생합니다.

long stkSize = stk.size(); // 얘때문에 시간초과 ,,,계속 ,,,
for(long j=0; j<stkSize; j++) {
	if(stk.peek()<=a) {
		stk.pop();
	}
}

아래와같이 while문을 사용해야 시간초과가 되지 않을 수 있습니다.

while(!stk.isEmpty() && stk.peek() <= a) {
    stk.pop();
}

---

3. 코드(JAVA) 

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

public 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> stk = new Stack<Integer>();
		
		long cnt = 0;
		for(int i=0; i<N; i++) {
			int a = Integer.parseInt(br.readLine());
			while(!stk.isEmpty() && stk.peek() <= a) {
				stk.pop();
			}
			cnt+=stk.size();
			stk.push(a);
		}
		
		bw.write(Long.toString(cnt));
		
		br.close();
		bw.close();
	}
}