C++로 문자열이 다양한(Diverse) 문자열인지 판별하는 방법

소문자 n개로 이루어진 문자열 S가 있다고 가정해 보겠습니다. 어떤 문자열이 영어 알파벳의 연속된 글자들로 구성되어 있고 각 글자가 정확히 한 번씩만 나타난다면, 이를 다양한(diverse) 문자열이라고 부릅니다. 단, 'a'와 'z'는 서로 인접하지 않은 것으로 간주합니다. 우리는 주어진 문자열이 다양한 문자열인지 아닌지 판별해야 합니다.

예를 들어 입력 문자열이 "fced"라면 출력은 True입니다. "fced"를 정렬하면 "cdef"가 되는데, 알파벳이 연속적으로 배치되어 있고 중복 글자도 없기 때문입니다.

해결 접근 방법

이 문제는 다음 단계를 통해 해결할 수 있습니다.

1. 문자열 S를 오름차순으로 정렬합니다.
2. flag 변수를 1로 초기화합니다.
3. i를 1부터 시작해 i가 문자열 길이보다 작고 flag가 0이 아닌 동안 반복하며 인접한 두 문자를 비교합니다.
4. S[i]에서 S[i-1]을 뺀 값이 1이 아니면, 즉 알파벳이 연속되지 않으면 flag를 0으로 설정합니다.
5. 반복이 끝난 후 flag가 여전히 0이 아니면 true를, 그렇지 않으면 false를 반환합니다.

C++ 구현 예제

더 쉽게 이해할 수 있도록 다음 C++ 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
bool solve(string S){
    sort(S.begin(), S.end());
    int flag = 1;
    for (int i = 1; i < S.size() && flag; i++)
        if (S[i] - S[i - 1] != 1)
            flag = 0;
    return flag ? true : false;
}
int main(){
    string S = "fced";
    cout << solve(S) << endl;
}

입력

"fced"

출력

1

코드 동작 원리

이 코드의 핵심은 정렬입니다. 문자열을 먼저 정렬하면, 다양한 문자열일 경우 알파벳 순서대로 차례대로 배치됩니다. 이후 인접한 문자들의 값 차이를 검사해 모든 차이가 1이라면 해당 문자열이 다양한 문자열임을 확인할 수 있습니다.

위 예제에서 "fced"는 정렬 후 "cdef"가 되며, 인접한 문자 간 차이가 모두 1이므로 함수는 true(1)를 반환합니다. 시간 복잡도는 정렬 과정이 지배하므로 O(n log n)입니다.