[Programmers/ level2] 모음사전🙄

👩문제

사전에 알파벳 모음 ‘A’, ‘E’, ‘I’, ‘O’, ‘U’만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 “A”이고, 그다음은 “AA”이며, 마지막 단어는 “UUUUU”입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

👩제한사항

• word의 길이는 1 이상 5 이하입니다.
• word는 알파벳 대문자 ‘A’, ‘E’, ‘I’, ‘O’, ‘U’로만 이루어져 있습니다.

👩입출력 예

word	result
“AAAAE”	6
“AAAE”	10
“I”	1563
“EIO”	1189

• 입출력에 대한 설명은 해당 사이트를 확인해주세요!

🙋‍♀️접근 방법

✍️ 완전탐색

• 가장 긴 문자열의 길이가 5이므로 모든 경우의 수를 구하는 방법을 이용할 수 있다.
• 구한 경우의 수를 sort()를 통해 정렬할 경우 사전순으로 정렬되기 때문에 word의 인덱스만을 구하면 된다.

from itertools import product

def solution(word):
    dic = []
    
    for i in range(1, 6):
        dic += list(map("".join, product('AEIOU', repeat = i)))
            
    dic.sort()
    return dic.index(word) + 1

🙄 여기에서 모든 경우의 수를 구하는 방식을 조금 더 자세히 살펴보자!

    for i in range(1, 6):
        dic += list(map("".join, product('AEIOU', repeat = i)))

• product는 곱집합을 구하는 함수로 repeat 값을 통해 원소의 중복 횟수를 결정할 수 있다.

🙄 repeat이 각각 1, 2일 때의 결과값을 확인하며 확실히 이해해보자!

    tmp1 = list(map("".join, product('AEIOU', repeat = 1)))
    tmp2 = list(map("".join, product('AEIOU', repeat = 2)))

tmp1: [‘A’, ‘E’, ‘I’, ‘O’, ‘U’]

tmp2: [‘AA’, ‘AE’, ‘AI’, ‘AO’, ‘AU’, ‘EA’, ‘EE’, ‘EI’, ‘EO’, ‘EU’, ‘IA’, ‘IE’, ‘II’, ‘IO’, ‘IU’, ‘OA’, ‘OE’, ‘OI’, ‘OO’, ‘OU’, ‘UA’, ‘UE’, ‘UI’, ‘UO’, ‘UU’]

🙂 따라서 "AEIOU"로 이루어진 1-5 길이의 모든 문자열을 구하기 위해서는 repeat의 값을 1-5로 바꿔가며 product 연산을 통해 곱집합을 구해야 한다.

✍️ 사전순 문자 사이의 거리를 이용한 풀이

위와 같이 모든 경우의 수를 구할 경우 그 만큼 시간이 오래 걸리게 된다.

완전탐색을 활용하지 않고 1-5번째 자리의 단어들이 어느 간격으로 바뀌는 지를 활용해 문제를 해결할 수 있다.

🙄 각각의 위치에서 단어들의 간격은 전체 문자열의 개수 / 특정 문자열 길이의 경우의 수를 통해 구할 수 있다. 그 이유는 해당 길이의 문자열들이 일정 간격 으로 전체 문자열 속에 존재하기 때문이다.

코드를 통해서 그 과정을 이해해보자!

def solution(word):
    max = 0
    for i in range(1, 6): # 전체 문자열의 개수 구하기
        max += 5**i
        
    result = 0
    for i in range(len(word)): # 가 문자의 위치마다 간격을 구해 더해나가는 과정
        if word[i] == "A":
            result += 1
        elif word[i] == "E":
            result += max//(5**(i+1))*1+1
        elif word[i] == "I":
            result += max//(5**(i+1))*2+1
        elif word[i] == "O":
            result += max//(5**(i+1))*3+1
        else:
            result += max//(5**(i+1))*4+1
    
    return result

🙄입력이 I일 때 진행되는 과정을 살펴보자!

• 전체 문자열의 개수를 구한다. = 3905

  

• 첫 번째 문자가 I가 되는 데의 간격을 구한다.
  • 첫 번째 자리의 경우 간격을 구한다.
    • 문자열 길이가 1인 문자열의 개수는 “A”, “E”, “I”, “O”, “U”로 5가지 이다.
    • 3905 / 5 = 781이 간격에 해당한다.
  • “I”의 순서를 구한다.
    • “AEIOU”에서 “I”는 두 번째 순서이다.
  • 따라서 781 * 2 = 1562가 해당 문자열이 나올 때까지의 총 간격이다.
• 첫 문자열에서 시작해 1562 후에 “I”가 나오는 것이므로 정답은 1562 + 1 = 1563!

✍️ 등비수열의 합 공식 이용

어떻게 등비수열이 적용이 되지? E가 몇 번째인지를 알아보는 다음의 그림을 보면 그 이유를 알 수 있을 것이다.

• 먼저 A로 시작하는 문자열의 경우의 수는 그림에서와 같이 공비가 5인 수들의 합을 통해 구할 수 있다.
• E는 “AEIOU”에서 첫 번째이다.
• 마지막으로 E 자신의 위치까지 더해야 하므로 +1을 해준다.

🙄 그렇다면 이를 적용한 풀이를 확인하며 게시글을 마무리해보자!

def solution(word):
    answer = 0
    
    for i, a in enumerate(word):
        answer += (5**(5-i)-1)/5-1 * "AEIOU".index(a) + 1

    return answer

이번 문제를 통해서 새까맣게 잊고 있었던 등비수열을 다시 떠올릴 수 있었다. 후에 내가 직접 문제 속 적용되는 등비수열을 발견할 수 있기를..😌

🙇‍♀️풀이에 부족한 부분이 있다면 말씀해주세요! 감사합니다!

📃 참고

• https://school.programmers.co.kr/learn/courses/30/lessons/84512
• https://school.programmers.co.kr/questions/25140
• https://velog.io/@powerful104/ProgrammersWeekly-Challenge5%EC%A3%BC%EC%B0%A8-%EB%AA%A8%EC%9D%8C-%EC%82%AC%EC%A0%84