C++에서 참조 문자열 순서를 기준으로 문자열 배열 정렬하기

문자열 배열과 하나의 참조 문자열이 주어졌다고 가정해 봅시다. 이때 참조 문자열에 나타난 문자들의 순서를 기준으로 문자열 배열을 정렬해야 합니다. 여기서는 배열 안의 문자열들과 참조 문자열이 모두 소문자 알파벳으로만 이루어져 있다고 가정합니다.

문제 예시

예를 들어 문자열 배열이 ["hello", "programming", "science", "computer", "india"]이고, 참조 문자열이 "pigvxbskyhqzelutoacfjrndmw"라고 합시다. 정렬 후의 결과는 다음과 같습니다.

["programming", "india", "science", "hello", "computer"]

즉, 일반적인 사전순(ASCII 순서)이 아니라 참조 문자열에서 각 문자가 등장하는 위치를 기준으로 정렬됩니다.

접근 방법

풀이 방법은 생각보다 단순합니다.

먼저 참조 문자열을 한 글자씩 순회하면서 unordered_map에 각 문자를 키(key)로, 해당 인덱스를 값(value)으로 저장합니다. 이렇게 하면 각 문자의 '우선순위'를 상수 시간에 조회할 수 있습니다.

그다음 정렬 시에는 ASCII 값이 아닌 이 맵을 기준으로 두 문자열을 비교합니다. 두 문자열의 같은 위치에 있는 문자 c1과 c2를 비교할 때, 맵에서 c1의 인덱스가 c2의 인덱스보다 작다면 c1이 더 앞에 오는 것입니다. 즉, c1 < c2로 판단합니다.

한쪽 문자열이 끝날 때까지 모든 문자가 동일하다면, 더 짧은 문자열을 먼저 배치하는 것이 자연스럽습니다.

구현 코드

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;

unordered_map<char, int> char_map;

bool compare(string c1, string c2) {
    for (int i = 0; i < min(c1.size(), c2.size()); i++) {
        if (char_map[c1[i]] == char_map[c2[i]])
            continue;
        return char_map[c1[i]] < char_map[c2[i]];
    }
    return c1.size() < c2.size();
}

int main() {
    string str = "pigvxbskyhqzelutoacfjrndmw";
    vector<string> v{ "hello", "programming", "science", "computer", "india" };
    
    char_map.clear();
    for (int i = 0; i < str.size(); i++)
        char_map[str[i]] = i;
    
    sort(v.begin(), v.end(), compare);
    
    // 정렬된 문자열 출력
    for (auto x : v)
        cout << x << " ";
}

실행 결과

programming india science hello computer

동작 원리 정리

참조 문자열 "pigvxbskyhqzelutoacfjrndmw"에서 'p'는 인덱스 0, 'i'는 인덱스 1, 'g'는 인덱스 2에 위치합니다. 따라서 'p'로 시작하는 "programming"이 가장 앞에 오고, 그다음 'i'로 시작하는 "india", 이후 's'로 시작하는 "science" 순으로 배치됩니다.

이 방식의 시간 복잡도는 맵 생성에 O(n), 정렬에 O(m log m × L)입니다. 여기서 n은 참조 문자열의 길이, m은 배열의 문자열 개수, L은 평균 문자열 길이를 의미합니다. unordered_map을 사용하면 문자 우선순위 조회가 O(1)이므로 전체적으로 매우 효율적입니다.