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

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

6198번: 옥상 정원 꾸미기

 

---

💻 풀이 결과

 

💯 최종 코드

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

class Building {
	int idx;
	int height;

	Building(int idx, int height) {
		this.idx = idx;
		this.height = height;
	}
}

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());
		int[] arr = new int[N];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		Stack<Building> stack = new Stack<>();
		// 각 옥상이 확인할 수 있는 갯수를 담을 배열
		int[] cnt = new int[N];
		for (int i = N - 1; i >= 0; i--) {
			// 맨 마지막 빌딩 검사할 때
			if (stack.isEmpty()) {
				stack.push(new Building(i + 1, arr[i]));
			}
			// 그다음부터 검사할 때
			else {
				while (true) {
					// 더이상 pop 할 것이 없다면 push 하고 종료
					if (stack.isEmpty()) {
						stack.push(new Building(i + 1, arr[i]));
						break;
					}
					// 현재 빌딩 > top
					if (arr[i] > stack.peek().height) {
						// 카운팅할 때가 중요한 것 같다 -> 내가 pop 하는 거 1개 + 내가 pop 하는 것이 pop 시킨 갯수
						cnt[i] += (1 + cnt[stack.peek().idx - 1]);
						// top 을 제거
						stack.pop();
					}
					// 현재 빌딩 <= top
					else {
						// push 하고 종료
						stack.push(new Building(i + 1, arr[i]));
						break;
					}
				} // while문 끝
			}
		} // for문 끝

		// 출력
		// 설마 long 으로 바꿔야하나...?
		long sum = 0;
		for (int i : cnt) {
			sum += i;
		}
		System.out.println(sum);
	}
}

 

💢 틀린 이유

• 빌딩의 개수 N의 범위가 80,000 이하이므로 옥상정원을 확인할 수 있는 총 수는 엄청 큰 수가 나올 수도 있는데 이때 합을 구하는 sum의 자료형을 int가 아닌 long으로 바꿔야 한다.

💬 풀이 과정

• Building 클래스를 생성한다.
• 맨 끝의 빌딩부터 차례로 스택의 top과 비교를 해준다.
• 원활한 비교를 위해서는 현재 바라보는 빌딩이 스택의 top보다 높다면 top을 삭제해야만 한다. 하지만 이 문제에서는 옥상을 바라볼 수 있는 빌딩의 수를 카운팅 해야 하는데, 삭제를 해버리면 카운팅을 할 수가 없다.
• 따라서 cnt 배열을 만들어 삭제를 하지 않은 빌딩들이 볼 수 있는 빌딩들의 수( pop 한 빌딩들 )를 저장하고 높이 비교를 할 때 pop을 하게 된다면 현재 pop을 하고 있는 빌딩 수 1개 + 내가 pop을 시킨 빌딩에서 바라볼 수 있었던 빌딩 수를 저장하면 된다.

💡 깨달은 점

1. 어려운 스택 활용 문제..

• 칭찬할 점 : 이 문제에서 pop을 한 빌딩들의 수를 어떻게 처리할까 고민하다가 cnt 배열을 만들어서 카운팅을 저장하고 pop을 할 때 카운팅한 수들을 어떻게 가져올지 잘 판단한 것 같다!
• 보완할 점 : 이러한 사고를 하기까지 시간이 꽤 걸렸다. 끝까지 검색을 하지 않고 해결한 부분은 잘했지만, 이러한 창의적인 사고를 좀 더 빠르게 할 수 있는 연습이 매우 필요하다.