BOJ 27536 - Stone Arranging 2

BOJ 27536 - Stone Arranging 2

스택의 관점에서 보면 현재 인덱스가 i라면 a[i]가 마지막으로 나오는 데(j)까지 모두 a[i]로 칠해줘도 된다. 이후에 i를 j + 1 로만들어준다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   vi ans = a;
   map<int, vi> idx;
   for (int i = 0; i < n; i++) idx[a[i]].pb(i);

   for (int i = 0; i < n;) {
      for (int j = i; j <= idx[a[i]].back(); j++) {
         ans[j] = a[i];
      }
      i = idx[a[i]].back() + 1;
   }
   for(int i: ans) cout << i << endl;
}