[고득점 Kit / 완전탐색] 모음사전

https://school.programmers.co.kr/learn/courses/30/lessons/84512

프로그래머스

 

각 자리의 알파벳 선택에 따라 그 이후에 나올 수 있는 가능한 단어의 개수를 계산해야 한다. 단어의 길이가 최대 5자리이기 때문에 각 자리에 있는 문자가 선택된 후 그 다음 자리에서 만들 수 있는 단어들의 개수를 더하면 된다.

우리는 자릿수별로 나올 수 있는 단어 개수를 미리 계산해 둔다. 예를 들면 다음과 같다.

• 첫 번째 자리에 문자가 정해지면, 그 뒤로 0~4자리까지 단어를 만들 수 있다.
• 예를 들어 첫 번째 자리가 "A"이면, 그 뒤로 "A", "AA", "AAA", "AAAA", "AAAAA" 등의 조합을 만들 수 있다.

 

아마 위의 설명으로는 이해하기 힘들 수 있다. 코드를 보며 이해해보자.

def solution(word):
    # 각 자릿수에서 해당 문자가 나왔을 때, 이후 가능한 단어 개수를 나타냄
    factors = [781, 156, 31, 6, 1]
    vowels = ['A', 'E', 'I', 'O', 'U']
    
    result = 0
    
    # word의 각 자리의 알파벳에 대해 해당 자릿수까지 몇 번째 단어인지 계산
    for i, char in enumerate(word):
        index = vowels.index(char)
        result += index * factors[i] + 1  # 해당 자리에 따른 가능한 모든 단어 개수 더하기
    
    return result

 

 

factors = [781, 156, 31, 6, 1]
vowels = ['A', 'E', 'I', 'O', 'U']

 

factors 배열: 각 자리에 따라 그 뒤에 나올 수 있는 단어의 개수를 미리 계산한 값이다.
이 배열은 사전적으로 모든 단어를 정렬할 때, 각 자리에서 문자가 결정되면 그 이후에 가능한 단어 수를 의미한다.

• factors[0] = 781: 첫 번째 자리가 정해졌을 때, 그 뒤에 나올 수 있는 단어 수. (5^4 + 5^3 + 5^2 + 5^1 + 5^0의 합)
• factors[1] = 156: 두 번째 자리가 정해졌을 때, 그 뒤에 나올 수 있는 단어 수. (5^3 + 5^2 + 5^1 + 5^0의 합)
• factors[2] = 31: 세 번째 자리 이후 가능한 단어 수. (5^2 + 5^1 + 5^0의 합)
• factors[3] = 6: 네 번째 자리 이후 가능한 단어 수. (5^1 + 5^0의 합)
• factors[4] = 1: 다섯 번째 자리 이후 가능한 단어 수. (5^0 = 1)

 

이해를 위해 예시를 들어보자.

 

네 번째 자리가 'A'일 때, 다섯 번째 자리를 생각해보면:

• "AAAA" (네 글자 단어)
• "AAAAA"
• "AAAAE"
• "AAAAI"
• "AAAAO"
• "AAAAU"

위처럼 총 6개의 단어가 나올 수 있다. 따라서, factors[3] = 6이다.

 

for i, char in enumerate(word):
    index = vowels.index(char)  # 'A' -> 0, 'E' -> 1, ...
    result += index * factors[i] + 1  # 해당 자리에 따른 가능한 모든 단어 개수 더하기

 

 

• for i, char in enumerate(word):
  • enumerate를 사용해 단어 word의 각 자리(char)와 그 자릿수(i)를 순서대로 탐색한다.
  • 예를 들어, 단어 "EIO"가 입력되었다면:
    • 첫 번째 자리: i = 0, char = 'E'
    • 두 번째 자리: i = 1, char = 'I'
    • 세 번째 자리: i = 2, char = 'O'
• index = vowels.index(char):
  • 각 자리에 있는 문자가 사전에서 몇 번째 문자인지 파악하기 위해 vowels.index(char)를 사용한다.
  • 'A'는 리스트에서 0번째, 'E'는 1번째, 'I'는 2번째, 'O'는 3번째, 'U'는 4번째에 위치한다.
  • 예를 들어 "EIO"에서:
    • 첫 번째 자리 char = 'E': index = 1
    • 두 번째 자리 char = 'I': index = 2
    • 세 번째 자리 char = 'O': index = 3
• result += index * factors[i] + 1:
  • 각 자리에서 가능한 단어 개수를 factors[i]와 곱하여 더해준다.
  • 예를 들어 첫 번째 자리에 'E'가 나오면, 사전에서 첫 번째 자리에 'A'로 시작하는 모든 단어가 끝난 뒤에 위치하므로, index = 1이 되고 factors[0] = 781이므로, 781만큼을 더한다.
  • +1은 해당 자리에 있는 단어 자체를 포함시키기 위한 값이다. (사전 순서가 1부터 시작하므로)

result 부분이 이해가 잘 안될 수 있다. 예시를 보며 이해해보자.

 

예시: "EIO"가 입력된 경우

1. 첫 번째 문자 'E':
   • i = 0 (첫 번째 자리)
   • char = 'E' (vowels.index('E') = 1, index = 1)
   • 첫 번째 자리가 'A'가 아닌 'E'이므로, 사전에서 'A'로 시작하는 모든 단어들을 건너뛰어야 한다.
   • factors[0] = 781 (첫 번째 자리에 문자가 고정되면 뒤에 가능한 단어의 개수)
   • result += 1 * 781 + 1 = 781 + 1 = 782
   첫 번째 자리에서 E가 사전에서 시작하는 모든 경우의 수는 782다. 즉, 첫 번째 자리에 'E'가 오면 'A'로 시작하는 모든 단어(781개)를 지나서, 자기 자신('E')부터 시작하게 된다.
2. 두 번째 문자 'I':
   • i = 1 (두 번째 자리)
   • char = 'I' (vowels.index('I') = 2, index = 2)
   • 두 번째 자리가 'A', 'E'가 아닌 'I'이므로, 그 이전 자리들을 건너뛰어야 한다.
   • factors[1] = 156 (두 번째 자리에 문자가 고정되면 뒤에 가능한 단어의 개수)
   • result += 2 * 156 + 1 = 312 + 1 = 313
   두 번째 자리가 'I'이면, 그 전에 'A'로 시작하는 단어들과 'E'로 시작하는 단어들(312개)을 지나서 'I'로 시작하는 단어로 넘어간다. 그 후에 자기 자신인 'I'를 포함하여 1을 더해준다.
3. 세 번째 문자 'O':
   • i = 2 (세 번째 자리)
   • char = 'O' (vowels.index('O') = 3, index = 3)
   • 세 번째 자리가 'A', 'E', 'I'가 아닌 'O'이므로, 그 이전 자리들을 건너뛰어야 한다.
   • factors[2] = 31 (세 번째 자리에 문자가 고정되면 뒤에 가능한 단어의 개수)
   • result += 3 * 31 + 1 = 93 + 1 = 94
   세 번째 자리가 'O'이면, 그 전에 'A', 'E', 'I'로 시작하는 단어들(93개)을 지나서 'O'로 시작하는 단어로 넘어간다. 그 후 자기 자신을 포함하여 1을 더해준다.

 

 

다른사람의 풀이를 확인해보니 등비수열의 합을 이용한 이런 좋은 풀이도 있었다.

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