Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++에서 문장의 단어를 길이순으로 재정렬하는 방법

문자열 처리 알고리즘 문제 중 하나로, 문장(sentence)의 단어들을 길이 순서대로 재정렬하는 방법을 C++ 코드와 함께 살펴보겠습니다.

문제 정의

여러 개의 단어로 이루어진 문자열이 있다고 가정해 보겠습니다. 이 문자열을 '문장'이라고 부르며, 다음과 같은 형식을 따릅니다.

  • 첫 글자는 항상 대문자입니다.
  • 문장 내 각 단어는 공백 문자 하나로 구분됩니다.

우리가 해야 할 일은 문장의 단어들을 길이가 짧은 순서(오름차순)대로 재배열하는 것입니다. 만약 두 단어의 길이가 같다면, 원래 문장에서 등장한 순서를 그대로 유지해야 합니다. 이는 안정 정렬(stable sort)의 성질을 활용해야 함을 의미합니다.

모든 단어를 재배열한 후, 첫 글자를 다시 대문자로 바꾸어 최종 문자열을 반환하면 됩니다.

예시

입력이 "I love to code in cpp"라면, 각 단어의 길이는 다음과 같습니다.

  • I (1), love (4), to (2), code (4), in (2), cpp (3)

길이순으로 정렬하면 1글자 'I', 2글자 'to'와 'in', 3글자 'cpp', 4글자 'love'와 'code' 순이 됩니다. 이때 길이가 같은 단어들은 원래 순서를 유지하므로, 출력 결과는 다음과 같습니다.

I to in cpp love code

해결 접근 방법

이 문제는 다음 단계를 거쳐 해결할 수 있습니다.

  1. 문장의 첫 글자를 소문자로 변환합니다. 대소문자가 섞인 상태에서 정렬하면 예상치 못한 결과가 나올 수 있기 때문입니다.
  2. 공백을 기준으로 문장을 분할(split)하여 단어 배열 x를 만듭니다.
  3. (단어, 원래 인덱스) 형태의 쌍(pair)을 저장할 배열 s를 선언하고, 각 단어와 그 인덱스를 함께 삽입합니다.
  4. 배열 s를 정렬합니다. 이때 비교 기준은 단어 길이 우선, 길이가 같다면 원래 인덱스 우선입니다.
  5. 정렬된 단어들을 공백으로 연결하여 결과 문자열 ret을 만듭니다.
  6. ret의 첫 글자를 대문자로 변환한 뒤 반환합니다.

C++ 구현 코드

아래는 위 알고리즘을 실제로 구현한 C++ 코드입니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector <string> split(string& s, char delimiter){
      vector <string> tokens;
      string token;
      istringstream tokenStream(s);
      while(getline(tokenStream, token, delimiter)){
         tokens.push_back(token);
      }
      return tokens;
   }
   static bool cmp(pair <string, int>& a, pair <string, int>& b){
      if(a.first.size() != b.first.size()) return a.first.size() < b.first.size();
         return a.second < b.second;
   }
   string arrangeWords(string text) {
      text[0] += 'a' - 'A';
      vector<string> x = split(text, ' ');
      vector<pair<string, int> > s;
      for (int i = 0; i < x.size(); i++)
      s.push_back({ x[i], i });
      sort(s.begin(), s.end(), cmp);
      string ret = "";
      for (int i = 0; i < s.size(); i++) {
         ret += s[i].first;
         if (i != s.size() - 1)
            ret += ' ';
      }
      ret[0] += 'A' - 'a';
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.arrangeWords("I love to code in cpp"));
}

코드 설명

  • split 함수: istringstream과 getline을 활용하여 구분자(공백)를 기준으로 문자열을 분할하고, 분할된 토큰들을 벡터에 담아 반환합니다.
  • cmp 함수: 정렬 기준을 정의하는 사용자 정의 비교 함수입니다. 단어 길이가 다르면 길이 오름차순으로, 같으면 저장된 인덱스 오름차순으로 비교하여 안정적인 정렬을 보장합니다.
  • arrangeWords 함수: 전체 로직을 수행하는 핵심 함수로, 첫 글자 소문자 변환 → 분할 → (단어, 인덱스) 쌍 생성 → 정렬 → 재조립 → 첫 글자 대문자 변환 순으로 진행됩니다.

실행 결과

입력:

"I love to code in cpp"

출력:

I to in cpp love code

시간 복잡도

문장을 n개의 단어로 분할했다고 할 때, 정렬에 O(n log n)의 시간이 소요되며, 분할과 재조립 과정은 O(n)입니다. 따라서 전체 시간 복잡도는 O(n log n)입니다. 추가로 단어 쌍을 저장하기 위해 O(n)의 공간 복잡도가 필요합니다.