[백준 2697] 다음수 구하기 (C#, C++) - soo:bak

문제 링크

2697번 - 다음수 구하기

설명

주어진 수와 자리수 구성은 같지만, 그 수보다 큰 수 중 가장 작은 수를 찾는 문제입니다.

• 입력으로 주어지는 수는 최대 80자리의 자연수이며,
• 각 테스트 케이스마다 해당 수의 다음 순열을 찾아야 합니다.
• 만약 사전순으로 다음에 올 수가 없다면 "BIGGEST"를 출력합니다.

다음 순열(Next Permutation) 알고리듬을 구현하거나 사용하는 전형적인 문제입니다.

접근법

입력 수는 문자열 형태로 주어지며, 각 자릿수를 하나의 문자로 처리할 수 있습니다.

문제의 핵심은 주어진 수보다 큰 수 중 가장 작은 수를 찾는 것이므로,

다음과 같은 다음 순열 구하기 절차를 그대로 따릅니다:

1. 뒤에서부터 오름차순이 깨지는 지점을 찾습니다.
2. 그 자리보다 큰 수 중 가장 오른쪽에 있는 수를 찾아 위치를 바꿉니다.
3. 바꾼 이후의 자릿수들은 오름차순으로 정렬하여 최소값을 구성합니다.

만약 위 절차에서 오름차순이 깨지는 지점을 찾을 수 없다면,

이미 가장 큰 수이므로 "BIGGEST"를 출력합니다.

관련 문제: [백준 10972] 다음 순열 (C#, C++) - soo:bak

관련 문제: [백준 10973] 이전 순열 (C#, C++) - soo:bak

---

Code

C#

using System;
using System.Linq;

class Program {
  static bool NextPermutation(char[] arr) {
    int i = arr.Length - 2;
    while (i >= 0 && arr[i] >= arr[i + 1])
      i--;
    if (i < 0) return false;

    int j = arr.Length - 1;
    while (arr[j] <= arr[i])
      j--;
    (arr[i], arr[j]) = (arr[j], arr[i]);
    Array.Reverse(arr, i + 1, arr.Length - i - 1);

    return true;
  }

  static void Main() {
    int t = int.Parse(Console.ReadLine());
    while (t-- > 0) {
      var input = Console.ReadLine().ToCharArray();
      if (NextPermutation(input)) Console.WriteLine(new string(input));
      else Console.WriteLine("BIGGEST");
    }
  }
}

C++

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

typedef vector<char> vc;

bool nextPermu(vc& p) {
  int n = p.size(), i = n - 2;
  while (i >= 0 && p[i] >= p[i + 1])
    --i;
  if (i < 0) return false;

  int j = n - 1;
  while (p[j] <= p[i])
    --j;
  swap(p[i], p[j]);
  reverse(p.begin() + i + 1, p.end());

  return true;
}

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

  int t; cin >> t;
  while (t--) {
    string s; cin >> s;
    vc p(s.begin(), s.end());
    if (nextPermu(p)) {
      for (char c : p)
        cout << c;
    }
    else cout << "BIGGEST";
    cout << "\n";
  }

  return 0;
}