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

www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

스택을 사용하는 문제이다. 리트코드에서 유사한 문제를 풀어본 경험이 있어서 접근하기가 어렵지 않았지만...

처음 보면 당황할 꺼 같다.

 

배열 사이즈가 꽤 크기 때문에 모든 배열에 대해 자기자신보다 큰 수가 나올때까지 카운트한다면 시간 초과가 날 것이다.

스택을 이용하여 거꾸로 배열을 순회하며 o(n)에 끝내도록 한다.

 

1. 맨 마지막 배열 인덱스를 넣는다.

2. 배열 인덱스를 n-2부터 0까지 돌면서 arr[stack의 top] 보다 현재 값이 크면 현재 인덱스를 푸쉬

3-1. 작거나 같으면(볼수 없으면) 

arr[stack.top()]이 현재 값보다 큰 값이 등장할때까지 pop한다. 이때 !stack.emtpy()조건을 꼭 붙이도록 하자.

3-2. 스택이 비어있는 상태라면 여태 값이 전부 pop됐다 == 현재 값보다 전부 작다 이므로 결과값에 n-1-curIdx를 더해준다.

#include <stdio.h>
#include <stack>

using namespace std;

int n;
int arr[80000];
stack<int> s;
int main(void)
{
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }

  long long cnt = 0;
  s.push(n - 1);
  for (int i = n - 2; i > -1; i--)
  {
    if (arr[i] < arr[s.top()])
    {
      s.push(i);
    }
    else
    {
      while (!s.empty() && arr[s.top()] < arr[i])
      {
        s.pop();
      }
      cnt += (s.empty()) ? n - 1 - i : s.top() - i - 1;
      s.push(i);
    }
  }
  printf("%lld\n", cnt);
  return 0;
}

스택이 비어있지 않다면 stack의 탑 값은 현재 값보다 크다는 의미이므로 결과값에 top - curIdx -1을 더해준다.

3-3. 현재 인덱스를 푸쉬한다.