백준 16923 : 다음 다양한 단어 C++

www.acmicpc.net/problem/16923

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	395	161	128	38.906%

---

문제

다양한 단어란 모두 다른 알파벳 소문자로만 이루어진 단어를 의미한다. 예를 들어, "codeplus", "coding", "algorithm"은 다양한 단어, "baekjoon", "startlink"는 다양한 단어가 아니다.

다양한 단어 S가 주어졌을 때, 사전 순으로 S의 바로 다음에 오는 다양한 단어를 구해보자.

---

입력

첫째 줄에 길이가 26보다 작거나 같은 다양한 단어 S가 주어진다.

---

출력

사전 순으로 S의 바로 다음에 오는 다양한 단어를 출력한다. 바로 다음에 오는 단어가 없는 경우에는 -1을 출력한다.

---

제한

 

 

---

예제 입력	예제 출력
codeplus	codeplusa
abc	abcd
zyxwvutsrqponmlkjihgfedcba	-1
abcdefghijklmnopqrstuvwzyx	abcdefghijklmnopqrstuvx

---

풀이 과정

 

입력되는 문자열의 길이가 26일 경우와 아닌 경우로 나눈다. 26일 경우 뒤에 올 수 있는 새로운 순열이 존재하는지 확인해야 하고 아닐 경우 -1을 출력해주면 끝나게 된다.

 

이때 새로운 순열을 찾는 방법은 next_permutation() 함수를 이용한다. next_permutation(arr, arr + N)은 배열 arr가 이루고 있는 상태에서 그다음에 올 수 있는 새로운 순열이 존재한다면 true 아니면 false를 반환한다. 즉, next_permutation() == true라는 것은, 그 다음에 출력할 수 있는 문자열이 존재한다는 뜻이기 때문에 그 문자열을 출력시키도록 구현하였다.

 

26이 아닐 경우 알파벳을 다 사용하지 않았으므로 문자열을 확인해 나오지 않은 알파벳 중에서 제일 앞에 있는 알파벳을 뒤에 붙여주는 것으로 구현한다.

 

---

C++ 코드

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>

#define endl "\n"
using namespace std;

int main(void)
{
    int alpha[26], Len;
    char abc[26];
    string Answer;
    memset(alpha, -1, sizeof(alpha));   //알파 배열를 -1로 초기화해주기
    string Temp; cin >> Temp;   //값 입력
    Len = Temp.length();        //길이 저장
    Answer = Temp;

    for (int i = 0; i < Len; i++){  //입력값 배열에 전달
        abc[i] = Temp[i];       
        alpha[abc[i] - 'a'] = i;
    }

    if (Len == 26) {    //26개일 경우 뒤에 올수있는 새로운 순열이 존재하는지 확인.
    //next_permutation(a, a + N) 배열 a 가 이루고있는 상태에서 다음 올 수 있는 새로운 순열이 존재한다면 true
        if (next_permutation(abc, abc + 27) == true) cout << abc << endl;//존재할 경우 해당 문자열 출력
        else cout << -1 << endl;            //아닐 경우 -1
    }
    else{       //26개가 안될경우 앞에서부터 확인해서 없는 단어 출력
        for (int i = 0; i < 26; i++) {
            if (alpha[i] == -1) {       //없으면 문자열 추가
                char C = (i + 'a');
                Answer = Answer + C;
                break;
            }
        }
        cout << Answer << endl;     //답 출력
    }

    return 0;
}