[백준] 6198 옥상 정원 꾸미기 #JAVA

 

BAEKJOON [6198] 옥상 정원 꾸미기

---

코드

---

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		long result = 0;	// (1+80000) /2 * 80000 > Integer.MAX_VALUE
		//System.out.println(Integer.MAX_VALUE);
		//> 2147483647
		int temp;	
		
		Stack<Integer> stack = new Stack<>();
		
		for (int i = 0; i < n; i++) {
			temp = Integer.parseInt(br.readLine());
			
			// 해당 건물 높이보다 같거나 작으면 삭제하여 처리한다.
			while(!stack.isEmpty() && stack.peek() <= temp) { //같은 층도 볼 수 없다.
				stack.pop();
			}
			
			result += stack.size();
			stack.push(temp);
				
		}
		
		System.out.println(result);
	}

}

 

 

 

풀이

---

• Stack 사용
• 해당 건물보다 낮은 건물을 스택에서 제외시킨다. (문제 조건 동일한 층수도 정원을 볼 수 없다.)
• result를 int 가 아닌 long으로 선언했는데 80000만개의 건물이 내림차순으로 있을 경우 int의 범위를 벗어난다. 3,200,040,000 이다. 

 

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)