BOJ 1467 - 수 지우기
원래 수가 이고 지워야할 수들의 집합이 라고 하자.
최종 정답의 길이는 이다.
정답에 첫 번째 올 숫자를 생각해보자.
으로 훑자. 각 숫자들의 인덱스를 미리 구해둔다.
에서 가장 먼저 나오는 위치가 라고 하자. 그 뒤에 나오는 위치인 를 생각했을 때,
가 정답에 추가되어야할 현재 수가 될 수 있다는 것은 정답에 마지막에 추가된 숫자의 에서의 위치가 일 때, 의 위치의 수들을 모두 지울 수 있어야 한다는 의미이다.
또한 가 이번 숫자로 올 수 있다면 항상 도 올 수 있으므로 각 숫자마다 현재 가장 처음에 있는 인덱스를 봐야한다.
어쨌든 가 올 수 있다면, 를 정답에 추가하고 인 에 대해 모두 지워준다.
까지 훑었는데 아무 숫자도 추가하지 못했다면 그냥 마지막 추가된 위치 + 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;
}
Comments