[BOJ]백준 16923번: 다음 다양한 단어

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

16923번: 다음 다양한 단어

다양한 단어 ? -> 모두 다른 알파벳 소문자로만 이루어진 단어

ex. coding, algorithm, ijin(x)

 

단어가 주어졌을 때 사전 상으로 주어진 단어의 바로 다음에 오는 단어를 출력하는 문제이다

다음 단어를 찾는 알고리즘을 구현하는 문제이다

이 문제의 풀이방법은 두 가지로 나뉜다.

1. 모든 알파벳이 다 포함된 단어일 때

2. 아닐 때

2번의 경우에는, 사용하지 않은 알파벳 중에 알파벳 순으로 가장 빠른 알파벳이 가장 뒤에 오면 된다.

ex. algorithm -> algorithmb / abcef -> abcefd

 

1번의 경우일 때는 조금 까다로운데, 사전 상 다음에 오는 알고리즘을 잘 생각해야 한다.

예제 4번에 나오는 abcdefghijklmnopqrstuvwzyx의 경우를 보자

abcdefghijklmnopqrstuvwzyx의 다음 단어가 abcdefghijklmnopqrstuvx인 이유는 뭘까?

사전의 순서는 트리와 유사한 구조를 가진다

옆의 트리가 있다고 했을 때, 사전순으로

A -> AB -> ABC -> ABD -> AC -> ... -> AZ순이다.

잘 보면, 트리는 다음 두 가지 특징을 가진다

① 특정 자식은 조상노드와 알파벳이 겹치지 않아야 한다.

② 전위순회(루트-왼-오)로 트리를 탐색할 경우 사전순으로 탐색이 가능하다!!

 

 

 

 

우리는 단어의 바로 다음에 오는 단어를 알아내야 한다

따라서, abcdefghijklmnopqrstuvwzyx의 경우에는 뒤에서부터 탐색을 했을 때

1. x -> 이미 앞의 글자들(조상노드들)에 x의 뒤 순서인 알파벳(y, z)이 있기 때문에 바꿀 수 X

2. y, z도 동일

3. w의 경우에는 w의 뒤 순서인 (x, y, z)가 앞의 글자들에 있는지 탐색했을 때 없기 때문에 w를 x로 바꾸고 바로 다음 글자를 null로 바꾸면 다음에 오는 단어 완성

 

해당 코드에서 사용한 apb배열은, 각 알파벳에 해당하는 글자의 위치를 저장하기 위해 사용했다.

#include <cstdio>
int apb[26], i = 0;	//각 알파벳의 위치를 저장하기 위한 배열
char s[27];	//문자열을 입력받는 배열
int main() {
	while (scanf(" %c", &s[i]) != EOF)	//한 글자씩 알파벳을 입력받는다
		apb[s[i++] - 'a'] = i + 1;	//apb 배열의 알파벳 위치에 입력받은 글자의 위치를 저장한다.
        //만약 acb라면, apb배열에는 {1, 3, 2, ...}가 저장됨
	if (i < 26) {
		for (int j = 0; j < 26; j++)
			if (!apb[j]) {
				s[i++] = j + 'a';
				printf("%s", s);
				return 0;
			}
	}
	else {
		for (int j = 25; j >= 0; j--)	//문자열의 뒤부터 탐색
			for (int k = s[j] - 'a' + 1; k < 26; k++)	//해당 글자의 뒤 순서 글자들을 탐색
				if (apb[s[j] - 'a'] < apb[k]) {	
                //만약 뒤 순서의 알파벳의 위치가 현재 글자보다 앞에 위치한다면
					s[j] = k + 'a';	//그 글자로 현재 글자를 교체하고
					s[j + 1] = '\0';	//다음 글자를 null문자로
					printf("%s", s);	//출력
					return 0;
				}
	}
	printf("-1");
	return 0;
}