백준 16923 - 다음 다양한 단어

https://www.acmicpc.net/problem/16923

풀이

이 문제는 크게 두 가지의 경우로 나눌 수 있다.

알파벳이 모두 들어있지 않은 경우

이 경우엔 없는 알파벳 중 가장 작은 알파벳을 맨 뒤에 붙이면 된다.

알파벳이 모두 들어있는 경우

먼저 zyxwvutsrqponmlkjihgfedcba는 사전순 가장 마지막이기 때문에 사전순으로 오는 다음 문자열이 없다. 이런 경우에만 -1을 출력해 주면 된다.

 

그렇지 않으면 문자열 $s$에서 가장 마지막으로 $s_{i} < s_{i + 1}$을 만족하는 $i + 1$를 찾자. 그리고 $i + 1$부터 순회해서 $s_{i}$보다 큰 가장 작은 알파벳 $x$를 찾아 $s$의 $i - 1$번째까지의 부분 문자열과 $x$를 출력하면 된다.

 

왜 나머지 문자를 지우냐면, 문자열의 사전순 비교는 길이가 작은 게 앞으로 오기 때문이다.

 

정답 코드 - C++

#pragma GCC target("fma,avx,avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")

#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"

using namespace std;

using ll = int_fast64_t;
using pii = pair<int, int>;

string s;

void solve()
{
  cin >> s;

  string target = "zyxwvutsrqponmlkjihgfedcba";
  if (s == target)
  {
    cout << -1;
    return;
  }

  set<char> a(begin(s), end(s));
  int sz = a.size();

  if (sz == 26)
  {
    int idx = -1;
    for (int i = 25; i > 0; i--)
    {
      if (s[i - 1] < s[i])
      {
        idx = i - 1;
        break;
      }
    }

    char ans = s[idx + 1];
    for (int i = idx + 2; i < sz; i++)
    {
      if (s[idx] < s[i] and ans > s[i])
      {
        ans = s[i];
      }
    }

    cout << s.substr(0, idx) << ans;
  }
  else
  {
    for (int i = 0; i < 26; i++)
    {
      if (!a.count(i + 'a'))
      {
        s.push_back(i + 'a');
        cout << s;
        return;
      }
    }
  }
}

int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  solve();
}