문제 개요
문자열 str1이 입력으로 주어집니다. 목표는 입력 문자열에서 동일한 문자가 연속으로 나타나는 쌍 사이에 '*'를 삽입하고, 재귀(recursion) 기법을 활용해 그 결과 문자열을 얻는 것입니다.
예를 들어 입력 문자열이 str1 = "wellness"라면, 연속된 문자 쌍 ll과 ss 사이에 *가 삽입되어 출력은 "wel*nes*s"가 됩니다.
예시
입력 − str1="happiness"
출력 − * 삽입 후 문자열: hap*pines*s
설명 − 연속된 문자 쌍 pp와 ss 사이에 *를 삽입하면 결과 문자열 hap*pines*s가 됩니다.
입력 − str1="swimmmmingggg pooool"
출력 − * 삽입 후 문자열: swim*m*m*ming*g*g*g po*o*o*ol
설명 − 연속된 문자 쌍 mm, gg, oo 사이에 *를 삽입하면 결과 문자열 swim*m*m*ming*g*g*g po*o*o*ol이 됩니다.
접근 방식
이 방법에서는 문자열 str1을 받아 각 단계마다 현재 인덱스를 기준점으로 삼아 str1을 두 부분으로 나눕니다. 앞쪽 부분 문자열의 마지막 문자와 뒤쪽 부분 문자열의 첫 번째 문자가 서로 같다면, 원본 문자열을 '부분 문자열1 + "*" + 부분 문자열2' 형태로 다시 설정합니다. 뒤쪽 부분 문자열의 길이가 0이 되면 재귀 호출을 종료합니다.
- 입력 문자열을 str1로 받고 그 길이를 len으로 계산합니다.
- 함수 addStar(string& s1, int i, int len1)은 s1, 문자열 길이, 현재 인덱스를 입력으로 받으며, 인접한 두 문자가 같을 경우 *를 삽입합니다.
- tmp1은 s1에서 인덱스 0부터 i까지의 부분 문자열입니다.
- tmp2는 s1에서 인덱스 i부터 len1+1까지의 부분 문자열입니다.
- tmp1의 마지막 문자와 tmp2의 첫 번째 문자가 같으면 s1 = tmp1 + '*' + tmp2로 설정합니다.
- 다음 위치를 검사하기 위해 addStar(s1, i+1, len1)을 재귀적으로 호출합니다.
- 모든 과정이 끝나면 main 함수 안에서 str1을 출력합니다.
예제 코드
#include <iostream>
using namespace std;
void addStar(string& s1, int i, int len1){
string tmp1=s1.substr(0,i);
string tmp2=s1.substr(i,len1+1);
if (tmp2.length() == 0){
return;
}
if (tmp1[i-1] == tmp2[0]){
s1 = tmp1 + '*' + tmp2;
}
addStar(s1, i+1, len1);
}
int main(){
string str1 = "aabbcccdddd";
int len=str1.length();
addStar(str1, 0, len-1);
cout << "String after adding * : "<<str1 << endl;
return 0;
}동작 원리
위 코드는 문자열 "aabbcccdddd"를 대상으로 addStar 함수를 호출합니다. 같은 문자가 n번 연속으로 나타나면 그 사이마다 *가 (n−1)개씩 삽입되므로, aa→a*a, bb→b*b, ccc→c*c*c, dddd→d*d*d*d처럼 변환되어 최종 결과가 만들어집니다. 참고로 매 호출마다 substr()로 새로운 문자열을 생성하기 때문에 전체 시간 복잡도는 O(n²) 수준입니다.
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
String after adding * : a*ab*bc*c*cd*d*d*d