길이가 n인 문자열 S가 있다고 가정해 봅시다. 어느 텍스트 편집기에는 독특한 규칙이 하나 있습니다. 이 편집기의 맞춤법 교정기는 단어 안에 두 개의 연속된 모음이 존재하는 한, 그중 첫 번째 모음을 삭제하는 방식으로 동작합니다. 연속된 모음이 더 이상 없으면 해당 단어를 올바른 단어로 간주합니다. 우리의 목표는 문자열 S에서 이렇게 교정된 최종 단어를 찾는 것입니다.
여기서 모음은 'a', 'e', 'i', 'o', 'u', 그리고 'y'입니다.
예를 들어 입력이 S = "poor"라면, 'o'가 연속으로 두 개 있으므로 앞의 'o' 하나가 삭제되어 출력은 "por"이 됩니다.
문제 해결 접근 방식
이 문제는 문자열을 한 번 순회하면서 인접한 두 문자가 모두 모음인지 확인하는 방식으로 해결할 수 있습니다. 핵심 로직은 다음과 같습니다.
- n을 문자열 S의 길이로 설정하고, 모음 집합 t를 "aeiouy"로 정의합니다.
- i = 1부터 n 미만까지 반복하면서 S[i]와 S[i-1]이 모두 모음인지 검사합니다.
- 둘 다 모음이라면 S에서 i번째 문자를 삭제하고, 인덱스가 밀리지 않도록 i를 1 감소시킵니다.
- 반복이 끝나면 교정된 문자열 S를 반환합니다.
C++ 구현 코드
아래 예제 코드를 통해 실제 구현 과정을 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
string solve(string S){
int n = S.size();
string t = "aeiouy";
for (int i = 1; i < n; i++){
if (t.find(S[i]) != -1 && t.find(S[i - 1]) != -1){
S.erase(i, 1);
i--;
}
}
return S;
}
int main(){
string S = "poor";
cout << solve(S) << endl;
}
입력
"poor"
출력
por
코드 상세 분석
코드의 핵심 부분을 살펴보면 다음과 같습니다.
- t.find(S[i]) != -1: 현재 문자가 모음 집합에 포함되어 있는지 확인합니다. find 함수는 문자를 찾지 못하면 -1을 반환하므로, -1이 아니라는 것은 해당 문자가 모음이라는 의미입니다.
- S.erase(i, 1): i번째 위치에서 길이 1만큼, 즉 현재 문자 하나를 삭제합니다.
- i--: 문자를 삭제하면 뒤의 문자들이 앞으로 당겨지므로, 인덱스를 하나 줄여야 다음 반복에서 건너뛰는 문자 없이 검사를 계속할 수 있습니다.
이 알고리즘은 최악의 경우 O(n²)의 시간 복잡도를 가집니다. erase 연산이 문자열의 나머지 부분을 이동시켜야 하기 때문입니다. 하지만 대부분의 실용적인 입력 크기에서는 충분히 효율적으로 동작합니다.