이 튜토리얼에서는 주어진 문자열을 고유한(distinct) 문자만 포함하도록 변환하는 C++ 프로그램을 살펴보겠습니다.
문제의 요구 사항은 다음과 같습니다. 하나의 문자열이 주어지며, 우리는 문자열을 처음부터 끝까지 순회하면서 중복해서 등장하는 모든 문자를 찾아낸 뒤, 아직 문자열에 존재하지 않는 다른 알파벳으로 교체해야 합니다. 최종 결과물의 모든 문자는 서로 달라야 합니다.
알고리즘 접근 방식
핵심 아이디어는 비교적 간단합니다.
먼저 문자열의 길이가 26을 초과하는지 확인합니다. 영어 소문자는 총 26개뿐이므로, 길이가 26보다 크면 모든 문자를 고유하게 만드는 것이 불가능하며 이 경우 -1을 반환합니다. 길이가 26 이하라면, 길이 26의 배열을 만들어 각 알파벳의 등장 횟수를 세고, 문자열을 다시 순회하면서 등장 횟수가 1보다 큰 중복 문자를 만날 때마다 해당 문자의 개수를 하나 줄인 후, 그 자리를 아직 사용되지 않은 알파벳으로 교체합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
//문자열에 아직 등장하지 않은 알파벳의 인덱스를 찾는 함수
int calculate_zero(int i, int occurrences[]){
while (i < 26) {
//한 번도 등장하지 않은 알파벳이라면
if (occurrences[i] == 0)
return i;
i++;
}
//모든 알파벳이 이미 한 번 이상 사용된 경우
return -1;
}
//수정된 문자열을 출력하는 함수
string print_modified(string str) {
int n = str.length();
//변환이 불가능한 경우
if (n > 26)
return "-1";
string ch = str;
int i, occurrences[26] = {0};
//각 문자의 등장 횟수를 계산
for (i = 0; i < n; i++)
occurrences[ch[i] - 'a']++;
int index = calculate_zero(0, occurrences);
for (i = 0; i < n; i++) {
//중복된 문자를 교체
if (occurrences[ch[i] - 'a'] > 1) {
occurrences[ch[i] - 'a']--;
ch[i] = (char)('a' + index);
occurrences[index] = 1;
//다음 미사용 알파벳으로 이동
index = calculate_zero(index + 1, occurrences);
}
}
cout << ch << endl;
}
int main() {
string str = "tutorialspoint";
print_modified(str);
}출력 결과
bucdrealspoint
코드의 동작 흐름을 정리하면 다음과 같습니다.
calculate_zero 함수는 인덱스 i부터 시작해 등장 횟수가 0인 알파벳, 즉 아직 문자열에 한 번도 나오지 않은 문자를 찾아 그 인덱스를 반환합니다. 만약 모든 알파벳이 이미 사용 중이라면 -1을 반환합니다. print_modified 함수는 먼저 문자열 길이가 26을 넘으면 변환이 불가능하다고 판단하고, 그렇지 않으면 각 알파벳의 빈도를 계산한 뒤 문자열을 순회합니다. 순회 중 빈도가 1보다 큰 중복 문자를 만나면 개수를 하나 줄이고, 그 위치를 현재 사용 가능한 알파벳으로 바꿉니다. 교체에 사용된 알파벳은 다시 선택되지 않도록 빈도를 1로 설정하고, 다음 후보 알파벳을 찾아 진행합니다.
이 방식은 문자열을 두 번만 순회하면 되므로 시간 복잡도는 O(n)이며, 알파벳 빈도 배열을 위한 공간만 추가로 필요하므로 공간 복잡도는 O(1)입니다.