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

---

문제 화면

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

문제 풀이

이 문제는 스택의 자료구조를 응용하는 문제이다.

건물이 일렬로 서있고 높이는 주어지는데 왼쪽에서 오른쪽만 볼 수 있다. 여기서 중요한 점은 현재 건물 (i라고 가정) 기준으로 오른쪽에 현재 건물보다 더 작은 건물(i+2라고 가정)이 있다고 해도 그 작은 건물의 왼쪽(i+1이라고 가정)에 더 큰 건물에 가려져 있다면 볼 수 없는 건물이 된다. 처음에 이부분을 신경을 안써서 애를 좀 먹었다. 각 건물이 볼 수 있는 수의 합을 구하는 것이기 때문에 그 말 그대로 ‘각 건물이 볼 수 있는 것’에 집중하다보면 O(n^2)의 알고리즘을 가장 먼저 떠올리게 되지만 그렇게 하면 시간초과가 나게 된다. 스택을 활용하여 O(n)의 알고리즘을 짜야 되고 그러기 위해서는 생각을 조금 바꿔서 스택을 사용해야 한다. 완성된 알고리즘의 핵심은 ‘내가 볼 수 있는 건물’에 초점을 맞추는 것이 아닌 ‘나를 볼 수 있는 건물’을 결과값으로 저장해서 계속 더해주는 방식이다.

제출 코드

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {

  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  int N;
  long long res = 0; // int로 하면 터진다
  stack<int> s; //res 값을 저장하기 위해 사용하는 스택 선언

  cin >> N ; // 건물의 수 입력받는다

  int arr[N]; // 입력받은 건물의 수 만큼 배열을 선언한다

  for(int i = 0 ; i < N ; i++) cin >> arr[i]; // 건물의 각각의 높이를 배열에 저장한다

  for(int i = 0 ; i < N ; i++) { // 배열 전체를 돌면서 각각의 건물에 대해 해당 알고리즘을 적용한다
    while(!s.empty() && s.top()<=arr[i]) s.pop(); 
      // 스택이 비지 않았고(처음 건물은 무조건 생략하게 됨) 바로 왼쪽의 건물이 현재 건물보다 작거나 같으면 없앤다 
      // 현재의 건물보다 작거나 같은 모든 건물들을 없앤다는 것은 현재 스택에서는 현재 인덱스의 건물보다 큰 건물만 남게 된다는 것 
      // 현재 건물보다 작은 건물들을 전부 없애도 되는 이유는 어차피 그 건물들은 현재 건물보다 오른쪽의 건물들 입장에서도 현재 건물에 가려져서 쓸모가 없다 
    res += s.size(); // 왼쪽에 있는 건물들중에 현재 건물보다 더 큰 건물(현재 건물의 옥상을 볼 수 있는 건물)만 남은 스택의 사이즈(개수)를 res 값에 더해준다
    s.push(arr[i]); // 현재 건물을 스택에 넣어준다
  }

  cout << res;
  
  return 0;
}

결론

이 문제는 스택을 얼마나 알고리즘에 응용해서 문제를 풀 수 있는지를 물어보는 문제이다. 알고리즘은 어렵지는 않은데 스택을 사용하여 생각해내기가 쉽지 않고 그래서 골드 티어로 지정된게 아닌가 싶다. 스택을 잘 사용한다는 것(스택 뿐만이 아니라 모든 자료구조가 마찬가지 인 것 같다)은 단순히 문법을 잘 안다는 것이 아닌 어떻게 알고리즘에 녹여서 활용할 수 있는지를 의미하는 것 같다.