C++로 시프트된 문자열 그룹화하는 방법

문자열이 하나 있다고 가정해 보겠습니다. 각 문자를 알파벳 순서상 바로 다음 문자로 "시프트"할 수 있으므로, 예를 들어 "abc"는 "bcd"로 바꿀 수 있습니다. 이 연산을 반복하면 "abc" → "bcd" → ... → "xyz"처럼 이어지는 수열이 만들어집니다. 이제 소문자 알파벳으로만 구성된 비어 있지 않은 문자열 목록이 주어졌을 때, 같은 시프트 수열에 속하는 문자열들을 모두 그룹으로 묶어야 합니다.

예를 들어 입력이 ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]라면 출력은 [["abc", "bcd", "xyz"], ["az", "ba"], ["acef"], ["a", "z"]]가 됩니다.

여기서 한 가지 눈여겨볼 점은 "az"와 "ba"가 같은 그룹에 속한다는 것입니다. 알파벳이 원형(circular)으로 이어져 있다고 가정하기 때문인데, 즉 'z' 다음에는 다시 'a'가 온다고 볼 수 있습니다.

알고리즘

이 문제를 해결하기 위해 다음 단계를 따릅니다.

• 맵(map) m을 하나 정의합니다.
• 2차원 배열 ret을 정의합니다.
• i := 0부터 strings의 크기 미만일 때까지 1씩 증가시키며 반복합니다.
  • key := 빈 문자열
  • j := 1부터 strings[i]의 크기 미만일 때까지 1씩 증가시키며 반복합니다.
    • diff := strings[i][j] − strings[i][j − 1]
    • diff < 0이면 diff := diff + 26
    • key := key에 "#"과 diff를 문자열 형태로 연결하여 추가
  • m[key]의 끝에 strings[i]를 삽입합니다.
• m의 각 원소 it에 대해 it의 값을 ret의 끝에 추가합니다.
• ret을 반환합니다.

핵심 아이디어는 인접한 두 문자 사이의 차이를 키로 사용하는 것입니다. 같은 시프트 수열에 속하는 문자열들은 문자 간 차이 패턴이 항상 동일하기 때문에, 이 패턴을 해시 맵의 키로 삼으면 자연스럽게 그룹화할 수 있습니다.

구현 예제

더 나은 이해를 위해 아래 C++ 구현을 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<vector<string>> groupStrings(vector<string>& strings) {
      unordered_map<string, vector<string> > m;
      vector<vector<string>> ret;
      for (int i = 0; i < strings.size(); i++) {
         string key = "";
         for (int j = 1; j < strings[i].size(); j++) {
            int diff = strings[i][j] - strings[i][j - 1];
            if (diff < 0)
               diff += 26;
            key += "#" + to_string(diff);
         }
         m[key].push_back(strings[i]);
      }
      unordered_map<string, vector<string>>::iterator it = m.begin();
      while (it != m.end()) {
         ret.push_back(it->second);
         it++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<string> v = {"abc","bcd","acef","xyz","az","ba","a","z"};
   print_vector(ob.groupStrings(v));
}

입력

{"abc","bcd","acef","xyz","az","ba","a","z"}

출력

[[az, ba],[a, z],[abc, bcd, xyz],[acef]]

복잡도 분석

시간 복잡도는 O(N × K)입니다. 여기서 N은 문자열의 개수, K는 각 문자열의 최대 길이입니다. 모든 문자열을 한 번씩 순회하면서 각 문자열의 키를 생성하기 때문입니다. 공간 복잡도 역시 O(N × K)로, 해시 맵에 저장되는 키와 값들이 이 범위 내에 있습니다.