Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 문자열 속 모음만 뒤집기 — 투 포인터 알고리즘 완벽 정리

문자열이 주어졌을 때, 해당 문자열에 포함된 모든 모음(vowel)만 골라서 순서를 뒤집는 것이 이번 문제의 목표입니다.

입력 예시 1 −

a = "tutor"

출력 −

totur

설명 − 문자열 "tutor"에서 모음 'u', 'o', 'u'의 위치와 순서를 서로 뒤바꾸면 결과는 "totur"가 됩니다.

입력 예시 2 −

a = "mathematics"

출력 −

mithametacs

설명 − 문자열 "mathematics"의 모음들만 역순으로 재배치하면 결과는 "mithametacs"가 됩니다.

문제 해결 접근 방식

주어진 문자열에서 모든 모음을 뒤집어야 합니다. 이 문제는 다양한 방법으로 풀 수 있지만, 선형 시간 O(n) 안에 해결하는 것이 핵심 조건입니다.

이를 위해 가장 효율적인 방법은 투 포인터(Two-Pointer) 기법입니다. 문자열의 양 끝을 가리키는 두 개의 포인터 low와 high를 준비하고, 처음에는 각각 가장 왼쪽 문자와 가장 오른쪽 문자를 가리키도록 설정합니다. 이후 두 개의 중첩 반복문을 돌면서 왼쪽 문자와 오른쪽 문자가 모두 모음일 때 두 문자를 서로 교환(swap)하고 포인터를 안쪽으로 이동시킵니다.

알고리즘 단계

  • 문자열을 입력받습니다.

  • 특정 문자가 모음인지 판별하는 불리언(Boolean) 함수를 작성합니다.

  • 문자열을 인자로 받아 그 안의 모음만 뒤집는 reverseVowel(string &str) 함수를 구현합니다.

  • 두 포인터 low와 high를 초기화하여 각각 첫 번째 문자('0'번째 인덱스)와 마지막 문자를 가리키게 합니다.

  • 양 끝의 문자가 모두 모음인지 확인하고, 모음이라면 제자리에서 두 문자를 교환한 후 오른쪽 포인터를 감소시킵니다.

  • 문자열의 모든 문자를 검사할 때까지 위 과정을 반복합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
bool isVowel(char ch) {
   return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' || ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U';
}
string reverseVowel(string &s){
   int low = 0;
   int high = s.size() - 1;
   while (low < high) {
      while (low < high && !isVowel(s[low])) {
         low ++;
      }
      while (low < high && !isVowel(s[high])) {
         high --;
      }
      swap(s[low++], s[high--]);
   }
   return s;
}
int main(){
   string a= "tutorialspoint";
   string ans= reverseVowel(a);
   cout<<ans;
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

titorailspount

입력 문자열 "tutorialspoint"에는 여러 개의 모음이 포함되어 있습니다. 투 포인터 기법으로 이 모음들의 위치만 서로 교환하면 최종적으로 "titorailspount"라는 결과를 얻을 수 있습니다.

이 알고리즘은 각 문자를 한 번씩만 검사하므로 시간 복잡도는 O(n)이며, 추가 공간 없이 원본 문자열 내에서(in-place) 처리하므로 공간 복잡도는 O(1)입니다.