문제 설명
길이가 n인 문자열 S가 주어졌다고 가정해 보겠습니다. S는 소문자로만 구성되어 있습니다. 우리는 0부터 n 사이의 값 k를 하나 선택한 뒤, S에서 k개의 문자를 골라 임의의 순서로 재배치해야 합니다. 이때 선택하지 않은 나머지 문자들은 원래 위치에 그대로 유지되며, 이 전체 연산은 정확히 한 번만 수행합니다.
목표는 문자열 S가 알파벳 순서(사전순)로 완전히 정렬되도록 만드는 k 값을 찾는 것입니다.
예를 들어 입력이 S = "acdb"라고 한다면 출력은 3이 됩니다. 첫 번째 문자 'a'는 이미 올바른 위치에 있고, 나머지 세 문자 'c', 'd', 'b'만 적절히 재배열하면 "abcd"가 되기 때문입니다.
풀이 접근 방법
이 문제의 핵심 아이디어는 매우 간단합니다. 원본 문자열과 정렬된 문자열을 자리별로 비교하면 됩니다. 먼저 문자열을 복사한 뒤 오름차순으로 정렬하고, 원본 문자열과 정렬된 문자열에서 서로 다른 문자가 있는 위치의 개수를 셉니다. 그 개수가 바로 재배열해야 하는 최소 문자 수 k입니다. 같은 위치에서 두 문자가 일치한다면 해당 문자는 이미 제자리에 있으므로 손댈 필요가 없기 때문입니다.
다음 단계를 따릅니다.
n := S의 길이
d := S (문자열 복사)
d를 오름차순 정렬
j := 0
i := 0부터 시작하여 i < n인 동안 i를 1씩 증가시키며 반복:
만약 S[i]가 d[i]와 같지 않다면:
j를 1 증가
j 반환
C++ 구현 예제
더 쉽게 이해할 수 있도록 다음 C++ 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(string S) {
int n = S.size();
string d = S;
sort(d.begin(), d.end());
int j = 0;
for (int i = 0; i < n; i++) {
if (S[i] != d[i])
j++;
}
return j;
}
int main() {
string S = "acdb";
cout << solve(S) << endl;
}
입력
"acdb"
출력
3
코드 설명
solve 함수는 먼저 입력 문자열의 복사본 d를 만들어 sort 함수로 오름차순 정렬합니다. 이후 for 반복문을 통해 원본 문자열 S와 정렬된 문자열 d를 인덱스별로 비교하면서, 두 문자가 다를 때마다 카운터 j를 1씩 증가시킵니다. 반복이 끝나면 j에는 재배열이 필요한 문자의 개수가 저장되며, 이 값이 곧 문제의 답이 됩니다.
예제에서 "acdb"를 정렬하면 "abcd"가 됩니다. 인덱스 0의 'a'는 두 문자열에서 일치하지만, 인덱스 1~3의 'c', 'd', 'b'는 각각 'b', 'c', 'd'와 다르므로 최종 카운트는 3이 됩니다. 이 알고리즘의 시간 복잡도는 정렬에 의해 지배되므로 O(n log n)입니다.