예를 들어 단어 “IO” 위치를 찾는다고 가정해봅시다. 이를 구할 수 있는 가장 직관적인 방법은 모든 단어 중 “IO”가 속한 위치를 찾는 것입니다.
▼ 표 5-4 “IO” 전후 인덱스와 단어들
|
인덱스 |
… |
2029 |
2030 |
2031 |
2032 |
2033 |
2034 |
2035 |
… |
|
단어 |
IIUUI |
IIUUI |
IIUUU |
IO |
IOA |
IOAA |
IOAAA |
얼핏 보기에는 모든 단어를 만들어 보는 것이 굉장히 비효율적인 것 같습니다. 문제 조건에 따라 만들 수 있는 단어 개수를 단어 길이별로 살펴봅시다. 각 자리에는 A, E, I, O, U 5개의 문자 중 하나가 들어갈 수 있으므로 단어 길이별 만들 수 있는 단어 개수는 다음과 같습니다.
▼ 표 5-5 단어의 길이별 만들 수 있는 단어 개수
|
단어 길이 |
만들 수 있는 단어 개수 |
|
1 |
5 |
|
2 |
52 |
|
3 |
53 |
|
4 |
54 |
|
5 |
55 |
이를 모두 더하면 총 만들 수 있는 단어 개수는 3,905개가 됩니다. 단어의 최대 길이가 5이므로 모든 단어의 문자를 순회한다면 최대 3905 * 5 = 19,525회가 됩니다. 이는 우리의 1초 기준인 1억 회에 한참 못 미치는 작은 수치이므로 만들 수 있는 모든 단어를 만들고, 실제 사전 위치를 찾아 주는 접근으로도 충분히 풀 수 있는 문제입니다.