[백준 29467] Cipher (C#, C++) - soo:bak

문제 링크

29467번 - Cipher

설명

소문자로 이루어진 문자열이 주어질 때, 그 안에서 사전순으로 가장 큰 부분 문자열을 찾아 출력하는 문제입니다.

접근법

사전순으로 가장 큰 부분 문자열은 항상 어떤 위치에서 시작하는 접미사입니다. 부분 문자열 뒤에 더 큰 문자가 있다면 그것을 포함하는 것이 항상 더 크기 때문입니다.

모든 시작 위치의 접미사를 비교하여 가장 큰 접미사를 찾으면 됩니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var s = Console.ReadLine()!;
    var best = 0;
    for (var i = 1; i < s.Length; i++) {
      var len = s.Length - Math.Min(i, best);
      var cmp = string.Compare(s, i, s, best, len, StringComparison.Ordinal);
      if (cmp > 0) best = i;
    }

    Console.WriteLine(s.Substring(best));
  }
}

C++

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

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

  string s; cin >> s;

  int best = 0, n = (int)s.size();
  for (int i = 1; i < n; i++) {
    if (s.compare(i, n - i, s, best, n - best) > 0)
      best = i;
  }

  cout << s.substr(best) << "\n";

  return 0;
}