[Lv2.] 모음사전

👉 사용 언어 : PYTHON3

모음사전

✅ Solution

from itertools import product

def solution(word):
    answer = 0
    prod = []
    for i in range(1, 6):
        prod.extend(list(product(['A', 'E', 'I', 'O', 'U'], repeat=i)))
    for j in range(len(prod)):
        prod[j] = ''.join(prod[j])
    return sorted(prod).index(word) + 1

 

👉 문제 설명 및 제한 사항

• 사전 : 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하 의 모든 단어 수록
  • ['A', 'AA', 'AAA', 'AAAA', 'AAAAA', 'AAAAE', 'AAAAI', 'AAAAO', 'AAAAU', 'AAAE', 'AAAEA', 'AAAEE', 'AAAEI', 'AAAEO', 'AAAEU', 'AAAI', 'AAAIA', 'AAAIE', 'AAAII', 'AAAIO', 'AAAIU', 'AAAO', 'AAAOA', 'AAAOE', 'AAAOI', 'AAAOO', 'AAAOU', 'AAAU', 'AAAUA', 'AAAUE', 'AAAUI', 'AAAUO', 'AAAUU', 'AAE', 'AAEA', 'AAEAA', 'AAEAE', ... ]
• 매개변수 : 단어 하나 word
  • 1 <= 길이 <= 5
  • 대문자 'A', 'E', 'I', 'O', 'U'로만❗️
• 리턴값 : 이 단어가 사전에서 몇 번째 단어인지❓

👉 아이디어

• 길이가 1 이상 5 이하 인 중복 순열로 배열을 생성한다.
• (반복)길이를 1번씩 지정할 수 있으므로 .extend()를 사용하여 배열 원소를 이어붙여준다.

• product를 사용하여 만든 중복 순열 결과값은 튜플 (=원소)로 이루어진 배열이다.
  • word와 같은 형태로 만들어주기 위해 결과값에서 반복문을 돌린 후, ''.join()을 통해 문자열("")로 묶어서 재할당한다.
• 최종 결과 배열에서 word 의 인덱스 를 찾고 순서(-번째)로 리턴해야하므로 +1 을 한 값을 리턴한다.

✅ itertools 라이브러리 내장 함수

• 순열
  
  • 반복 가능한 객체(=길이가 n인)에 대해서 중복을 허용하지 않고 r개를 뽑아서 나열
  • permutations(반복 가능한 객체, r)
  • 순서 의미 O
• 조합
  • 반복 가능한 객체(=길이가 n인)에 대해서 중복을 허용하지 않고 r개를 뽑기
  • combinations(반복 가능한 객체, r)
  • 순서 의미 X
• 중복 순열
  • product(반복 가능한 객체, repeat=1)
  • (EX1) product([1,2,3],'ab') > [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b'), (3, 'a'), (3, 'b')]
  • (EX2) product([1,2,3], repeat=2) > (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1) (3, 2) (3, 3)
• 중복 조합
  • combinations_with_replacement(반복 가능한 객체, r)

✅ 다른 사람 풀이 참고

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

 

👉 깨달은 것 / 알게된 것

• 등비수열의 합을 이용하여 위와 같이 풀이할 수 있다.
  • 0이상 N이하 인 문자열들의 개수의 일반항 a(N) = (N+1)^0 + (N+1)^1 + ... + (N+1)^N
    • (N + 1)^k ( 길이가 k인 문자열 개수 )
  • 첫째항(= 첫번째 문자열 길이) a = 1
  • 공비 r = 5
• itertools 라이브러리의 내장 함수 product 를 사용하여 중복 순열을 구할 수 있다.
  • itertools 라이브러리의 내장 함수를 사용하면, 직접 구현하는 것보다 실행시간을 약 1/10 줄일 수 있다.

✅ 사전 순서 참고 링크 : https://school.programmers.co.kr/questions/58885