[ 백준 16923 ] 다음 다양한 단어 (C++)

백준의 다음 다양한 단어(16923) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 주어진 입력 다음에 오는 '다양한 단어'를 출력하는 문제이다. 먼저 본인은 크게 2가지로 나눠보았다.

   바로 입력되는 문자열의 길이가 26이냐 아니냐 로 나눴다.

   26이 의미하는 것은 알파벳의 갯수이다. 알파벳은 총 26개이고, 문자열의 길이가 26이라는 것은

   입력된 문자열에서 모든 알파벳을 사용했다는 것이고, 사전 순으로 그 다음에 출력할 문자열이 있으면 그 문자열을

   출력하고, 그게 아니라면 -1을 출력하도록 구현하였다.

   또 하나는 26이 아니라는 것이다. 즉, 26이 아니라는 것은 그 다음에 또 다른 문자가 올 수 있다는 것이다.

   그런데 생각을 해보자. bcd 라는 문자열이 입력됬을 때 그 다음 입력되는 다양한 단어는 무엇일까?

   바로 bcda 라는 것을 별 생각 없이 알 수 있다. 즉, 문자열의 길이가 26이 아닐 때는, 현재 문자열에서 나오지 않은

   알파벳 중에 제일 앞에 있는 놈을 뒤에 붙여주기만 하면 다음 다양한 단어가 될 수 있다.

   따라서, 본인은 Alphabet[26]이라는 int형 배열을 만들어서, 초기값을 -1로 설정해 주었고, 각 문자들이 저장되는

   Index번호를 저장해 주었다. 즉, bcd가 입력됬을 때, Alphabet[0](a를 의미) = -1 일 것이고, Alphabet[1](b를 의미)

   = 0 이 저장되어 있을 것이다.

   즉, 길이가 26이 아닐 때에는 저 Alphabet[] 배열을 통해서 가장 처음으로 나오는 -1이 나오는 문자를 입력된

   문자열에 뒤에 추가하는 식으로 구현해 보았다.

  

   그렇다면 이제는 길이가 26일때를 생각해보자. 길이가 26이라는 말은, 이미 입력된 문자열에서 26개의 알파벳을

   모두 사용했다는 말이고, 기존의 방법처럼 그 뒤에 어떤 알파벳을 추가한다는 것은 불가능하다.

   본인은 이 부분을 고민을 하다가 next_permutation() 함수를 이용해서 구현해보았다.

   next_permutation(a, a + N)은, 배열 a가 이루고 있는 상태에서 그 다음에 올 수 있는 새로운 순열이 존재한다면

   true를 반환, 그게 아니면 false를 반환하는 함수이다.

   즉, next_permutation() == true라는 것은, 그 다음에 출력할 수 있는 문자열이 존재한다는 뜻이기 때문에 그 문자열을

   출력시키도록 구현하였고, 그게 아니라면 -1을 출력하도록 구현해 보았다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
 
#define endl "\n"
using namespace std;
 
int Alphabet[26], Len;
char Inp[26];
string Answer;
 
void Input()
{
    memset(Alphabet, -1, sizeof(Alphabet));
    string Temp; cin >> Temp;
    Len = Temp.length();
    for (int i = 0; i < Len; i++)
    {
        Inp[i] = Temp[i];
        Alphabet[Inp[i] - 'a'] = i;
    }
    Answer = Temp;
}
 
void Solution()
{
    if (Len == 26)
    {
        if (next_permutation(Inp, Inp + 27) == true)
        {
            cout << Inp << endl;
        }
        else cout << -1 << endl;
    }
    else
    {
        for (int i = 0; i < 26; i++)
        {
            if (Alphabet[i] == -1)
            {
                char C = (i + 'a');
                Answer = Answer + C;
                break;
            }
        }
        cout << Answer << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}