오등큰수

Problem link: https://www.acmicpc.net/problem/17299

요약하면 뒤 부터 풀었고, 스택을 활용해서 풀었다.

요상하게도(?) 데이터 구간에 대해 무언가를 쿼리할 때 서로 다른 키 값을 사용해야하는 경우에 스택, 스위핑, 구간트리를 활용하면 문제가 쉽게 풀리는 경향이 있다.

이 문제는 골3따리 답게 스택정도를 활용해주면 쉽게 풀린다.

사전에 해쉬를 활용해서 숫자의 빈도를 구해놓자.

이제 배열을 뒤에서부터 스캔하면서 top -> bottom 방향이 빈도의 내림차순으로 유지되는 스택을 관리하자.

어떤 새로운 원소 x를 볼 차례라고 해보자.

배열을 뒤부터 보고 있으므로, 스택 내에 있는 원소들은 당연히 x보다는 오른편에 위치하던 원소들이다.

F[x]보다 작은 빈도 값을 갖는 스택 내의 원소들은 한 개씩 pop해서 삭제해주어도 이후 답에는 영향이 없다.

이는 이후에 보게될 어떤 수 y에 대해서,

• F[y] < F[x]라면 어차피 x가 y의 오등큰수가 될 것이며,
• F[y] >= F[x]라면 F[x]보다 작은 수들은 y의 오등큰수가 될 수 없기 때문이다.

pop연산 이후에 스택의 top에 있는 원소가 곧 x의 오등큰수가 된다.

물론, x의 오등큰수를 구한 뒤에 x도 스택에 넣어주어야 한다.

위의 조건을 만족하도록 스택을 관리해나가면서 각 원소의 오등큰수를 구해주면 답을 구할 수 있다.

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

using namespace std;

const int kMaxN = 1000000;

int N;
int A[kMaxN];
int F[kMaxN + 1];

void Solve()
{
  stack<int> answer;
  stack<pair<int, int> > st;

  for (int idx = N - 1; idx >= 0; --idx)
  {
    while (!st.empty() && st.top().first <= F[A[idx]])
    {
      st.pop();
    }

    answer.emplace(st.empty() ? -1 : st.top().second);
    st.emplace(F[A[idx]], A[idx]);
  }

  while (!answer.empty())
  {
    cout << answer.top() << ' ';
    answer.pop();
  }
  cout << '\n';
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Input
  cin >> N;
  for (int it = 0; it < N; ++it)
  {
    cin >> A[it];
    ++F[A[it]];
  }

  // Solve
  Solve();

  return 0;
}