이 문제의 목표는 문자열 배열을 정렬된 순서로 출력하되, 정렬 과정에서 한 문자열을 다른 문자열에 복사하는 작업을 수행하지 않는 것입니다. 즉, 프로그래머는 정렬 중에 실제 문자열 데이터를 이동시키거나 복사할 수 없습니다.
문제 이해하기
예시를 통해 개념을 더 쉽게 이해해 보겠습니다.
입력 : {"Delhi", "Hyderabad", "Indore", "Mumbai", "Banglore"}
출력 : Banglore, Delhi, Hyderabad, Indore, Mumbai설명 − 위 결과는 사전순(lexicographical order)으로 정렬된 것입니다. 'B'로 시작하는 Banglore가 가장 앞에 오고, 'M'으로 시작하는 Mumbai가 마지막에 위치하게 됩니다.
해결 방법
이 문제를 해결하기 위해 문자열 자체의 위치를 변경하는 대신, 각 문자열의 올바른 인덱스를 저장하는 별도의 배열을 생성하는 방법을 사용할 수 있습니다. 문자열의 실제 위치를 바꾸려면 복사가 필요하기 때문에, 인덱스만 조작하면 복사 없이 정렬 효과를 얻을 수 있습니다.
구체적으로는 인덱스 배열(index array)을 만들어 선택 정렬(selection sort) 기법으로 정렬한 뒤, 정렬된 인덱스 순서대로 원본 문자열을 출력합니다. 선택 정렬은 직접 비교를 통해 최솟값을 찾아가는 방식으로, 이 문제에 적합합니다.
알고리즘 동작 방식
- 0부터 n-1까지의 값을 담은 인덱스 배열을 초기화합니다.
- 선택 정렬을 수행하되, 문자열끼리 직접 교환하는 대신
compare()함수로 비교하여 인덱스 배열의 요소만 교환(swap)합니다. - 정렬이 완료된 인덱스 배열을 따라 원본 문자열 배열을 순서대로 출력합니다.
구현 예제
이제 프로그램을 작성하여 동작을 확인해 보겠습니다.
#include <iostream>
using namespace std;
void sortedStringArray(string arr[], int n){
int stringIndex[n];
int i, j, min;
// 인덱스 배열 초기화
for (i=0; i<n; i++)
stringIndex[i] = i;
// 선택 정렬: 인덱스만 교환
for (i=0; i<n-1; i++){
min = i;
for (j=i+1; j<n; j++){
if (arr[stringIndex[min]].compare(arr[stringIndex[j]]) > 0)
min = j;
}
if (min != i){
int temp = stringIndex[min];
stringIndex[min] = stringIndex[i];
stringIndex[i] = temp;
}
}
// 정렬된 인덱스 순서대로 문자열 출력
for (i=0; i<n; i++)
cout << arr[stringIndex[i]] << ", ";
}
int main(){
string arr[] = {"Delhi", "Hyderabad", "Indore", "Mumbai", "Banglore"};
int n = 5;
sortedStringArray(arr, n);
return 0;
}
출력 결과
Banglore, Delhi, Hyderabad, Indore, Mumbai,
핵심 포인트 정리
- 인덱스 배열 활용: 문자열 자체를 복사·교환하지 않고, 문자열이 저장된 위치(인덱스)만 정렬하여 원본 데이터를 그대로 유지합니다.
- compare() 함수: C++의
string::compare()메서드를 사용해 두 문자열을 사전순으로 비교합니다. 반환값이 0보다 크면 앞의 문자열이 뒤의 문자열보다 사전순으로 뒤에 온다는 의미입니다. - 시간 복잡도: 선택 정렬을 사용하므로 시간 복잡도는 O(n²)입니다. 문자열 복사가 발생하지 않기 때문에 긴 문자열을 다룰 때 복사 비용을 절약할 수 있다는 장점이 있습니다.