9081 단어 맞추기

주어지는 단어에서, 단어안의 알파벳으로만 이루어진 단어를 사전순으로 나타낸다고 할 때, 주어진 단어의 다음번에 나오는 단어를 출력하는 문제이다.

이 문제를 풀기 위해선 단어를 정렬하는 과정이 필요한데, 문제는 어떤단어를 얼마나 정렬하는가 이다. 내가 푼 방법은 단어의 끝부터 시작하여 알파벳을 고르고, 그 알파벳을 앞의 알파벳과 비교하면서 위치를 바꿨을 때 사전순으로 뒷서는지를 검사한다. 그런 알파벳이 여러개 존재할 때는, 바꾸는 위치가 가장 뒤로가 있는것(변화가 가장 작은것)을 택한다.

만약 그런 알파벳이 존재하지 않으면 그대로 뿌리면 되고, 존재해서 찾았다면 고른 알파벳을 찾아낸 위치에 끼워 넣는다. 그리고 그 뒤의 문자열을 오름차순으로 정렬해주면 된다.

소스