안녕하세요! 오늘은 BOJ 6198 - 옥상 정원 꾸미기 문제를 풀어볼게요.
접근 - Step 1
문제가 굉장히 친절하게 그림까지 그려줘서, 상황에 대한 이해가 어렵진 않을 것 같아요.
i번째 빌딩에서는 i번째 빌딩의 오른쪽 빌딩만 볼 수 있고, 자신이 위치한 빌딩보다 높이가 높거나 같은 빌딩의 옥상은 볼 수 없어요.
모든 빌딩의 관리인들이 확인할 수 있는 빌딩 수의 합을 구해주는 것이 문제예요.저는 이렇게 추측하고 시작했어요: "빌딩들에 번호가 붙어 있다고 생각을 해보면, 다음으로 들어오는 건물의 높이가 나보다 낮으면 카운팅 해주고, 나보다 높이가 높거나 같은 건물이 들어올 경우에는 카운팅을 중단하면 되지 않을까?"
예시를 한 단계씩 쪼개서 살펴보면서, 어떻게 구현해야 할지 감을 잡아볼게요.
왼쪽 빌딩부터 번호를 붙여서 차례차례 확인해 볼게요.
높이가 10인 첫 번째 빌딩이 먼저 있을 것이고, 높이가 5인 두 번째 빌딩이 오른쪽에 들어와요.
그러면 첫번째 빌딩에서는 두번째 빌딩의 옥상을 확인할 수 있으니, 현재 확인 가능한 빌딩 수는 1이에요.
이제 높이가 7인 세 번째 빌딩이 가장 오른쪽에 들어설 거예요.
여기서 높이가 5인 두 번째 빌딩은 세 번째 빌딩보다 높이가 낮으니 가로막혀서, 세 번째 빌딩부터 N번째 빌딩까지의 옥상을 확인할 수 없어요.
두 번째 빌딩은 확인 가능한 빌딩 옥상의 수가 0인 상태로 카운팅을 중단해야 해요.
첫 번째 빌딩은 높이가 10이니 세 번째 빌딩 옥상을 확인할 수 있으니 카운팅을 계속해야 하겠네요.
이제 높이가 4인 네 번째 빌딩을 볼게요.
높이가 7인 세 번째 빌딩에서는 네 번째 빌딩 옥상을 볼 수 있으니, 카운팅을 해주어야 해요.
두 번째 빌딩은 이미 가로막혀서 카운팅이 중단되었으니 확인할 필요가 없어요.
첫 번째 빌딩도 네 번째 빌딩 옥상을 볼 수 있으니, 카운팅을 해주어야 해요.
마지막으로 높이가 12인 다섯 번째 빌딩이 가장 오른쪽에 들어섰어요.
네 번째 빌딩은 다섯 번째 빌딩보다 높이가 낮으니 가로막혀서, 다섯 번째 빌딩부터 N번째 빌딩까지의 옥상을 확인할 수 없어요.
세 번째 빌딩과 첫 번째 빌딩 또한 다섯 번째 빌딩보다 높이가 낮아서, 마찬가지로 다섯번째 빌딩부터는 옥상을 확인할 수 없고, 카운팅을 중단해야 해요.
접근 - Step 2
저는 여기에서 자료구조 스택을 떠올렸어요.스택은 LIFO(Last In First Out) 자료구조인데, 예시가 아주 적절한 지는 잘 모르겠지만, 가능한 쉽게 설명해 볼게요.
배스킨라빈스에서 아이스크림을 먹으려고 파인트를 산다고 해보면, 세 가지 맛을 고를 수 있는데 처음 고른 맛을 밑에서부터 쌓아서 주잖아요?그린티 → 베리베리 스트로베리 → 민트초코 순으로 골라서, 그 순서대로 쌓아서 담아줬다고 생각해 볼게요.결국 마지막에 고른 맛이 제일 위에 쌓여있으니, 가장 먼저 먹을 수 있는 맛은 제일 마지막에 고른 맛인 민트초코예요.
이처럼, 스택 자료구조는 처음 들어간 데이터가 가장 마지막에 나오고, 가장 마지막에 들어간 데이터가 가장 처음 나오는 자료구조예요.스택에서는 맨 위의 원소를 보는 top()과 스택의 가장 위에 원소를 넣는 push(), 가장 마지막에 넣은(= 가장 위에 있는) 데이터를 빼는 pop(), 비어있는지 확인하는 empty()와 같은 함수를 지원해요.원칙적으로는 배열처럼 특정 위치의 데이터를 바로 확인할 수는 없어요.그렇다면 매번 빌딩이 새로 스택에 들어올 때마다, for문을 돌려서 모든 원소에 대해 빌딩의 높이와 비교해서 더 높으면 카운트 변수를 1 증가시키고 그 외의 경우에는 pop()하는 방법과 같이 구현하는 것은 불가능할 것 같아요.
스택에 i번째 빌딩을 새로 담을 때, i번째 빌딩보다 높이가 높은 건물만 스택에 남기는 것으로 구현해 보는 것은 어떨까요?스택의 가장 위에 쌓인 원소인 top()을 확인해 보았을 때, i번째 빌딩보다 높이가 낮거나 같으면, i번째 빌딩부터 N번째 빌딩까지 전부 가로막혀서 확인할 수 없으니까 카운팅 하면 안 되니, 스택에서 pop()해서 빼버리는 거예요.이때, pop() 하기 전에 확인가능한 빌딩 수를 더해주는 것이 필요한데, 몇 번째 빌딩인지(index)를 높이와 함께 pair로 담아주면 될 것 같아요.i번째 빌딩보다는 높이가 낮거나 같지만, i-1번째 빌딩까지는 확인 가능한 빌딩이니 확인 가능한 빌딩의 수는 index - i - 1로 구해낼 수 있을 것 같아요.
방금 살펴본 예시로, i = 3인 세 번째 빌딩을 스택에 담을 때, 현재 스택에는 { {10, 1} , {5, 2} }가 담겨있어요.
스택의 맨 위 원소(= 마지막에 담은 원소)는 두 번째 빌딩인 {5, 2}이니, 세 번째 빌딩보다 높이가 낮아요.
스택에서 빼낼 건데, i - 1 = 2번째 빌딩까지는 확인할 수 있을 것이고, index가 2이니, 2 - 2 = 0개의 건물을 확인할 수 있어요.
아직 이해가 어려우시다면, 다섯 번째 빌딩까지 위의 예시를 통해서 한번 생각해 보시는 것도 좋을 것 같아요.
그래도 이해가 안 되신다면 저의 설명 능력 부족 탓입니다.. 아래에 다시 한번 코드를 바탕으로 단계별로 설명해 드렸으니 한 번만 더 고민해 주세요!
구현
#include <iostream>
#include <stack>
using namespace std;
stack<pair<int, int>> s;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
long long result = 0;
for (int i = 0; i < n; i++) {
int height;
cin >> height; // 건물의 높이를 받아옴
while (!s.empty() && height >= s.top().first) { // 스택이 비었을 경우 예외처리
// 기존 건물들을 담은 스택에서 새로 스택에 담을 건물보다 높이가 더 높은 건물이 나올 때까지 pop
result += (i - s.top().second - 1); // 확인 가능한 건물 수를 결과에 더해줌
s.pop(); // 높이가 낮은 건물들은 스택에서 빼냄
}
s.push({height, i}); // i번째 건물이고, 높이 height인 건물을 스택에 담음
// 결국 스택에는 i번째 건물보다 높이가 높은 건물만 남게 됨
}
while (!s.empty()) { // 만일 스택에 원소가 남았으면 계산
if (s.top().second == n-1) { // 결국 마지막 빌딩 옥상에선 다음 건물을 볼 수 없으므로 예외처리
s.pop();
continue;
}
result += (n - 1 - s.top().second); // 마지막 건물까지 볼 수 있던 것이므로 확인 가능한 건물 수를 결과에 더해줌
s.pop();
}
cout << result;
return 0;
}
살짝 복잡해 보이지만, 잘 뜯어서 살펴보면 그렇게까지 어렵지 않아요.
다시 한번 단계별로 설명을 드릴게요.
처음 빌딩의 높이를 받아왔을 경우에는, 스택이 비었으니 pair로 빌딩의 높이와 몇 번째 빌딩인지 index를 같이 스택에 담아줘요.
두 번째부터 빌딩의 높이를 받아왔을 때에는 스택에 원소가 있고, 이번 빌딩의 높이가 스택에 담은 가장 마지막 빌딩(top)의 높이보다 같거나 더 높을 경우에는, 가장 마지막에 스택에 담긴 빌딩은 이제 가로막혀서 N번째 빌딩까지 옥상을 확인할 수 없다는 뜻이에요.
아까 예시로 확인했던 카운팅을 중단해야 하는 상황인 거죠?
그러면 다음 빌딩부터는 옥상을 확인할 수 없으니 스택에서 빼낼 건데, 이때 확인 가능한 빌딩 수를 어떻게 구할지 생각해 보면, 이번 빌딩(= i번째 빌딩)은 확인할 수 없다는 것은 바로 전 빌딩(= i-1번째 빌딩)까지는 확인이 가능했다는 것이겠죠?
그리고 빌딩에 번호(index)를 붙여주었으니, 몇 번째로 들어온 빌딩인지는 s.top().second로 확인할 수 있어요. (pair로 {높이, index}를 담았기 때문이에요.)
그러니, 확인할 수 있는 빌딩의 수는 i - 1 - s.top().second로 구해낼 수 있어요.
이를 while문 안에서 스택에 i번째 빌딩보다 높은 빌딩이 남을 때까지 반복해요.
이렇게 N개의 빌딩의 높이를 받아서 처리를 해준 뒤에, 마지막으로 스택에 최소한 마지막 빌딩인 N-1번째 빌딩이 남아있을 거예요.
그런데 마지막 빌딩에서 오른쪽을 바라봤을 때에는 아무 빌딩 옥상도 확인할 수 없겠죠? 이에 대한 예외처리를 해줬어요.
그리고 나머지 남아있는 스택의 원소들은, 마지막 빌딩보다 높이가 높아서 마지막 빌딩까지 확인할 수 있던 빌딩들일 거예요.
그러므로 N - 1 - s.top().second로 확인할 수 있는 빌딩의 수를 구할 수 있어요.
이를 while문 안에서 스택에 남은 원소가 없을 때까지 반복해요.
마지막으로, 확인할 수 있는 빌딩의 수의 합인 결과 result를 출력하면 돼요.
높이의 범위가 굉장히 크기 때문에, 결과 result가 long long 자료형을 사용해야 해요.
저는 이걸 놓치는 안일함에 한 번 틀렸네요. ㅠㅠ
최대한 공들여서 작성하는 데 노력했지만, 이해가 안 되는 부분이 있다면 꼭 질문해 주세요. 감사합니다!
