B. The String Has a Target
가장 작은 문자의 가장 뒤에 있는 인덱스를 골라주면 된다.
일단 가장 작은 문자를 골라야 하는 이유는 항상 가장 작은 문자가 가장 먼저 앞에 나오게 만들어줄 수 있기 때문이다.
가장 작은 문자들 중 가장 뒤의 것을 골라야 하는 이유는 다음과 같다.
가장 작은 문자가 나오는 인덱스를 i1,i2,⋯(i1<i2<⋯) 라 하자.
i1을 제일 앞으로 보낸다면 결과 문자열 t는 가장 작은 문자가 a 이고 원본 문자열이 s라면
t1=as1,i1−1si1+1,n 이 된다. i2 를 이용해 하면
t2=as1,i2−1si2+1,n 이 된다.
잘 보면 prefix가 일치하다가 가장 먼저 문자가 달라지는 시점(i=i1+1)에 t2 에선 a 가 나오고 t1 에선 그렇지 않다.
따라서 가장 뒤에 것을 제일 앞으로 보내는게 최적이다.
void solve() {
int n;
cin >> n;
string s;
cin >> s;
vi mx(26, -1);
for (int i = 0; i < n; i++) {
maxa(mx[s[i] - 'a'], i);
}
auto get_sub = [&](int l, int r) -> string {
if (l > r) return "";
return s.substr(l, r - l + 1);
};
for (int i = 0; i < 26; i++) {
if (mx[i] == -1) continue;
cout << string(1, char(i + 'a')) + get_sub(0, mx[i] - 1) + get_sub(mx[i] + 1, n - 1) << endl;
break;
}
}
Comments