[BOJ] 3015: 오아시스 재결합 (C/C++)

문제 3015번: 오아시스 재결합

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서 있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

출력

서로 볼 수 있는 쌍의 수를 출력한다.

문제분석

문제 요구사항

• 두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B 보다 큰 사람이 없어야한다.
• 서로 볼 수 있는 싸의 수를 구하는 프로그램을 작성해야한다.

Stack을 A 또는 B 보다 큰 사람이 없게 유지 시킨다.

구현

Stack의 top에 저장된 키를 이용하여 Stack의 top의 키가 지금 현재 키보다 크다면 pop 하고 ans에 top에 저장된 사람 수만큼 더 해준다.
이 과정을 맞친 후, stack에 사람이 있다면 ans에 1을 더 한다.
위 과정을 다 끝낸 후 stack의 현재 값을 push 한다.

증명

해당 증명은 Stack을 이용하는 경우에 Stack의 활용법에 더 가깝습니다.
Stack에 가장 깊숙히 들어있는 요소를 첫 번째, Stack에 top에 있는 요소를 마지막 요소라 칭하겠습니다.

예제를 통하여 증명 해보자. 백준 사이트를 보게 되면 예제로 [2, 4, 1, 2, 2, 5, 1]의 입력을 받는다고 나와있다.
구현부에 첫 파트를 보게 되면, stack의 마지막키는 stack의 마지막이 아닌 키들 보다 작을 수 밖에 없다.
이러한 성질이 적용 됨으로, Stack의 내부 요소들은 Descending order(내림차순)으로 정리되어 있다는 성질을 하나 유추 할 수 있다.

이제 Stack의 모든 요소들에 대하여 생각해보자. Stack의 모든 요소들의 경우 현재 사람보다 늦게 push된 요소들은 자기 보다 키가 낮다. 즉, Stack에 있는 요소들은 현재 사람을 무조건 보는 것이 가능한 상태 이다.
현재 사람 입장에서 생각해 보자면 Stack에 있는 사람들중 현재 사람보다 키가 작은 사람부터 현재 사람보다 키가 처음으로 큰 사람까지 볼 수 있게 된다. 이렇게 서로 볼 수 있는 쌍을 Stack을 이용하여 밝혀 내는 것이 가능하다.

첫 번째로 Stack의 top의 키가 현재 사람보다 작은 경우, 현재 사람 뒤의 미래의 사람들은 현재 사람에 막혀 보지 못함으로, Stack의 top은 이 시점에서 부터 불필요한 정보가 된다. 답에 같은 키를 가진 사람들을 더한 후 pop을 진행한다.

두 번째로 Stack의 top의 키가 현재 사람과 같은 경우, 여러명이 있을 수 있기 때문에 std::pair<int,int>를 사용, 첫 번째에는 사람의 키, 두 번째에는 동일한 키인 사람의 수를 count하여 기록한다. 답에 Stack에 push되어있던 같은 키를 가진 사람들의 수 만큼 답에 더해준다. 그 후 편의를 위하여 pop을 진행한다.

세 번째로 Stack의 top의 키가 현재 사람보다 큰 경우, 현재 사람뒤의 미래 사람들은 볼 수 있음으로, 유용한 데이터이다. 따라서 해당 데이터를 pop하지 않고 Stack에 남겨둔다.
이때 현재 사람과 stack의 top도 서로 볼 수 있는 한 쌍이 됨으로 답을 1 증가시킨다.

코드

#include <iostream>
#include <stack>
#include <utility>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);

  int N;
  std::cin >> N;

  long long ans = 0;
  std::stack<std::pair<int, int>> stk;

  int person, cnt_same_height_people;
  for (int i = 0; i < N; ++i) {
    cnt_same_height_people = 1;
    std::cin >> person;

    while (!stk.empty() && stk.top().first <= person) {
      ans += stk.top().second;
      if (stk.top().first == person) {
        cnt_same_height_people = stk.top().second + 1;
      }
      stk.pop();
    }

    if (!stk.empty()) {
      ans++;
    }
    stk.push({person, cnt_same_height_people});
  }
  std::cout << ans;

  return 0;
}