문자열에 포함된 알파벳들을 사전순(오름차순)으로 재배열하고, 문자열 안에 있는 모든 숫자들의 합을 뒤에 이어 붙이는 문제를 살펴보겠습니다.
문제 예시
입력 : str = "adv4fc3" 출력 : "acdfv7" 설명 : 모든 알파벳은 "acdfv"로 정렬되고, 그 뒤에 숫자 4와 3의 합인 7이 붙습니다. 입력 : str = "h2d7e3f" 출력 : "defh12" 설명 : 모든 알파벳은 "defh"로 정렬되고, 그 뒤에 숫자 2, 7, 3의 합인 12가 붙습니다.
해결 접근 방법
이 문제에서 수행해야 할 작업은 두 가지입니다. 하나는 문자열을 정렬하는 것이고, 다른 하나는 숫자 값들을 더하는 것입니다.
문자열 정렬 : 문자열에 등장하는 각 알파벳의 개수를 세어 저장한 뒤, 개수만큼 해당 문자를 새 문자열에 삽입하는 방식으로 정렬된 문자열을 만들 수 있습니다. 이는 카운팅 기반 정렬(계수 정렬)과 유사한 방식입니다.
숫자 합산 : 문자열을 탐색하면서 숫자가 나타날 때마다 별도의 변수에 값을 누적하여 합계를 구할 수 있습니다.
C++ 구현 코드
위 접근 방식을 C++ 코드로 구현하면 다음과 같습니다.
#include<bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
int main(){
string str = "h2d7e3f";
int ch[26] = {0};
int count = 0;
// 문자열의 모든 문자를 탐색합니다.
for (int i = 0; i < str.length(); i++){
// 각 알파벳의 등장 횟수를 셉니다.
if (str[i]>='a' && str[i] <='z')
ch[str[i] - 97] = ch[str[i] - 97] + 1;
// 숫자를 만나면 합계에 더합니다.
else
count = count + (str[i]-'0');
}
string final = "";
// ch 배열을 이용해 정렬된 문자열을 만듭니다.
for (int i = 0; i < 26; i++){
char a = (char)('a'+i);
// 현재 문자를 개수가 소진될 때까지 새 문자열에 삽입합니다.
while (ch[i]-- != 0)
final = final + a;
}
// 마지막으로 숫자들의 합을 문자열 뒤에 붙입니다.
if (count>0)
final = final + to_string(count);
cout << "재배열된 문자열: " << final;
return 0;
}실행 결과
재배열된 문자열: defh12
코드 상세 설명
알파벳은 총 26개이므로, 각 알파벳의 등장 횟수를 저장하기 위해 크기 26의 배열
ch를 초기화합니다.첫 번째 반복문에서는 문자열을 처음부터 끝까지 탐색합니다. 알파벳을 만나면 해당 알파벳의 개수를 증가시키고, 숫자를 만나면
count변수에 값을 더합니다.두 번째 반복문에서는
ch배열에 저장된 개수 정보를 바탕으로 정렬된 새 문자열을 만듭니다. 각 문자를 자신의 개수만큼 문자열에 추가합니다.마지막으로 첫 번째 반복문에서 계산한 숫자들의 합을 문자열 끝에 덧붙여 최종 결과를 완성합니다.
복잡도 분석
이 알고리즘은 문자열을 한 번 탐색한 뒤 고정된 크기(26)의 배열을 한 번 순회하므로, 시간 복잡도는 O(N)(N은 문자열 길이)입니다. 추가로 사용하는 공간은 크기 26의 배열뿐이므로 공간 복잡도는 O(1)로 매우 효율적입니다.
결론
이번 튜토리얼에서는 해시 테이블(카운팅 배열) 접근 방식을 활용하여 문자열 내 알파벳을 정렬하고 숫자의 합을 이어 붙이는 문제를 해결했습니다. C++ 코드와 함께 동작 원리도 자세히 살펴보았습니다. 이 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 튜토리얼이 여러분에게 도움이 되기를 바랍니다.