예를 들어 단어 “IO” 위치를 찾는다고 가정해봅시다. 이를 구할 수 있는 가장 직관적인 방법은 모든 단어 중 “IO”가 속한 위치를 찾는 것입니다.

▼ 표 5-4 “IO” 전후 인덱스와 단어들

얼핏 보기에는 모든 단어를 만들어 보는 것이 굉장히 비효율적인 것 같습니다. 문제 조건에 따라 만들 수 있는 단어 개수를 단어 길이별로 살펴봅시다. 각 자리에는 A, E, I, O, U 5개의 문자 중 하나가 들어갈 수 있으므로 단어 길이별 만들 수 있는 단어 개수는 다음과 같습니다.

▼ 표 5-5 단어의 길이별 만들 수 있는 단어 개수

이를 모두 더하면 총 만들 수 있는 단어 개수는 3,905개가 됩니다. 단어의 최대 길이가 5이므로 모든 단어의 문자를 순회한다면 최대 3905 * 5 = 19,525회가 됩니다. 이는 우리의 1초 기준인 1억 회에 한참 못 미치는 작은 수치이므로 만들 수 있는 모든 단어를 만들고, 실제 사전 위치를 찾아 주는 접근으로도 충분히 풀 수 있는 문제입니다.