BOJ 1467 - 수 지우기

BOJ 1467 - 수 지우기

원래 수가 $S$이고 지워야할 수들의 집합이 $T$라고 하자.

최종 정답의 길이는 $n(S)-n(T)$ 이다.

정답에 첫 번째 올 숫자를 생각해보자.

$9 \to 0$ 으로 훑자. 각 숫자들의 인덱스를 미리 구해둔다.

$9$에서 가장 먼저 나오는 위치가 $i$라고 하자. 그 뒤에 나오는 위치인 $j~(i < j)$를 생각했을 때,

$i$가 정답에 추가되어야할 현재 수가 될 수 있다는 것은 정답에 마지막에 추가된 숫자의 $S$에서의 위치가 $i'$ 일 때, $i' < k < i$ 의 위치의 수들을 모두 지울 수 있어야 한다는 의미이다.

또한 $S_j$ 가 이번 숫자로 올 수 있다면 항상 $S_i$ 도 올 수 있으므로 각 숫자마다 현재 가장 처음에 있는 인덱스를 봐야한다.

어쨌든 $i$가 올 수 있다면, $S_i$ 를 정답에 추가하고 $i' < k < i$ 인 $k$에 대해 모두 지워준다.

$9 \to 0$ 까지 훑었는데 아무 숫자도 추가하지 못했다면 그냥 마지막 추가된 위치 + 1의 숫자를 추가해주면 된다.

void solve() {  
   int n;  
   string s, t;  
   cin >> s >> t;  
   n = sz(s);  
   vi remove_cnt(10);  
   vector<deque<int>> digit_idx(10);  
   for (char c: t) remove_cnt[c - '0']++;  
   for (int i = 0; i < n; i++) digit_idx[s[i] - '0'].pb(i);  
  
   int nxt_add_idx = 0;  
  
   string ans;  
   auto insert = [&](int i) {  
      ans += s[i];  
      for (int d = 0; d < 10; d++) {  
         while (sz(digit_idx[d]) && digit_idx[d][0] <= i) digit_idx[d].pop_front();  
      }  
      for (int j = nxt_add_idx; j < i; j++) remove_cnt[s[j] - '0']--;  
      nxt_add_idx = i + 1;  
   };  
  
   for (int l = 0; l < n - sz(t); l++) {  
      for (int d = 9; d >= 0; d--) {  
         if (sz(digit_idx[d]) && sz(digit_idx[d]) == remove_cnt[d]) {  
            continue;  
         }  
         if (!sz(digit_idx[d])) continue;  
         vi cnt(10);  
         int can_remove = 1;  
         for (int j = nxt_add_idx; j < digit_idx[d][0]; j++) {  
            cnt[s[j] - '0']++;  
            if (cnt[s[j] - '0'] > remove_cnt[s[j] - '0']) {  
               can_remove = 0;  
               break;  
            }  
         }  
         if (can_remove) {  
            insert(digit_idx[d][0]);  
            break;  
         }  
      }  
      if (sz(ans) != l + 1) insert(nxt_add_idx);  
   }  
   cout << ans;  
}