정렬된 형식으로 문자열을 정렬하기 위해 얼마나 많은 문자를 재배열해야 하는지를 찾는 C++ 프로그램

n개의 문자가 있는 문자열 S가 있다고 가정합니다. S는 소문자만 포함합니다. 0에서 n 사이의 숫자 k를 선택한 다음 S에서 k 문자를 선택하고 임의의 순서로 치환해야 합니다. 이 과정에서 나머지 문자는 변경되지 않습니다. 우리는 이 전체 작업을 정확히 한 번만 수행합니다. 우리는 k의 값을 찾아야 하며, 이에 대해 S는 알파벳 순서로 정렬됩니다.

따라서 입력이 S ="acdb"와 같으면 'a'가 올바른 위치에 있고 나머지 문자를 재배열해야 하므로 출력은 3이 됩니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n := size of S
d := S
sort the array d
j := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   if S[i] is not equal to d[i], then:
      (increase j by 1)
return j

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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