C++ 코드: 'trygub'가 부분 수열이 되지 않도록 문자열 재배열하기

소문자 영어 알파벳 n개로 이루어진 문자열 S가 있다고 가정해 봅시다. 우리는 S의 문자들을 재배열하여, 결과 문자열에서 "trygub"가 부분 수열(subsequence)로 나타나지 않도록 만들어야 합니다.

예를 들어, 입력이 S = "pintontrygubabc"라면 출력은 "abbcginnoprttuy"가 됩니다.

해결 접근 방법

이 문제는 의외로 아주 간단하게 해결할 수 있습니다. 다음 두 단계만 거치면 됩니다.

문자열 S를 오름차순으로 정렬한다
정렬된 S를 반환한다

왜 정렬만으로 해결될까요?

문자열을 알파벳 순서로 정렬하면 모든 문자가 사전순으로 배치됩니다. "trygub"가 부분 수열이 되려면 t → r → y → g → u → b 순서로 문자가 등장해야 하는데, 정렬된 문자열에서는 'r'이 항상 't'보다 앞쪽에 위치합니다. 따라서 't' 다음에 'r'이 나오는 경우가 존재할 수 없으므로, "trygub"는 절대 부분 수열이 될 수 없습니다.

예제 코드

아래의 C++ 구현을 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
string solve(string S){
    sort(S.begin(), S.end());
    return S;
}
int main(){
    string S = "pintontrygubabc";
    cout << solve(S) << endl;
}

입력

"pintontrygubabc"

출력

"abbcginnoprttuy"