[백준 1251] 단어 나누기 (C#, C++) - soo:bak

문제 링크

1251번 - 단어 나누기

설명

소문자로 이루어진 단어가 주어지는 상황에서, 단어(길이 3~50)가 주어질 때, 단어를 세 부분으로 나누고 각 부분을 뒤집어 이어붙인 결과 중 사전순으로 가장 앞서는 문자열을 구하는 문제입니다.

세 부분의 길이는 각각 1 이상이어야 하며, 각 부분을 뒤집은 후 원래 순서대로 이어붙입니다. 예를 들어 “mobitel”을 “mo”, “bi”, “tel”로 나누면 각각을 뒤집어 “om” + “ib” + “let” = “omiblet”이 됩니다.

접근법

단어의 길이가 최대 50으로 작으므로 모든 가능한 분할을 시도할 수 있습니다.

첫 번째 분할 위치는 1번째부터 마지막에서 2번째까지, 두 번째 분할 위치는 첫 번째 분할 다음부터 마지막 직전까지 가능합니다. 이렇게 하면 세 부분의 길이가 모두 1 이상이 보장됩니다.

각 분할에 대해 세 부분을 각각 뒤집은 후 이어붙이고, 지금까지 발견한 결과 중 사전순으로 가장 앞서는 것을 유지합니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static string Reverse(string text) {
      var chars = text.ToCharArray();
      Array.Reverse(chars);
      return new string(chars);
    }

    static void Main(string[] args) {
      var word = Console.ReadLine()!;
      var length = word.Length;
      string? result = null;

      for (var i = 1; i < length - 1; i++) {
        for (var j = i + 1; j < length; j++) {
          var part1 = Reverse(word.Substring(0, i));
          var part2 = Reverse(word.Substring(i, j - i));
          var part3 = Reverse(word.Substring(j));
          var candidate = part1 + part2 + part3;
          
          if (result == null || String.CompareOrdinal(candidate, result) < 0)
            result = candidate;
        }
      }

      Console.WriteLine(result);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string word; cin >> word;
  int length = word.length();
  string result;

  for (int i = 1; i < length - 1; i++) {
    for (int j = i + 1; j < length; j++) {
      string part1 = word.substr(0, i);
      string part2 = word.substr(i, j - i);
      string part3 = word.substr(j);
      
      reverse(part1.begin(), part1.end());
      reverse(part2.begin(), part2.end());
      reverse(part3.begin(), part3.end());
      
      string candidate = part1 + part2 + part3;
      if (result.empty() || candidate < result)
        result = candidate;
    }
  }
  
  cout << result << "\n";
  
  return 0;
}