[프로그래머스 lv 2] 모음사전

사용 언어 - Python3

문제 - 모음사전

프로그래머스

 

 

정답

순열조합 완전탐색 or 규칙 찾는 문제 (정답 맞춘 여부 X)

정답 풀이

1. product(리스트, repeat=반복횟수) 중복순열 이용하기

product는 처음 알게되었다.

product(리스트, repeat=반복횟수) : 중복 순열. 1부터 5까지 반복해야하기 때문에 for문으로 구현한다.

words 빈리스트에 list(중복순열)을 append해서 모든 가능한 조합을 저장한다.

그 뒤 words리스트를 sort 정렬을 하고, index를 찾는다.

index는 0부터 세기 때문에 +1을 해줘야한다.

product로 5번만 중복되기 때문에 시간복잡도가 적어서 문제 해결이 가능하다.

# 정답1
from itertools import product

def solution(word):
    words = []
    for i in range(1,6):
        for c in product(['A','E','I','O','U'],repeat=i):
            words.append(''.join(list(c)))
    words.sort()
    answer = words.index(word) + 1
    
    return answer

 

2. (5+1)*5+1 규칙 이용하기

입력값의 오른쪽 끝자리(일의 자리)는 5개 알파벳이 올 수 있고, 그 다음 십의 자리에서 다른 알파벳으로 넘어간다.

5가지 알파벳 + 앞의 자릿수 숫자 바꾸기 1회 = 5+1을 자릿수만큼 반복해주면 된다.

(5+1) = 일의 자리 경우의 수

(5+1)*5+1 = 십의 자리

((5+1)*5+1)*5+1 = 백의 자리

(((5+1)*5+1)*5+1)*5+1 = 천의 자리

단어수는 총 5개 이기 때문에 4번 반복해준다고 생각하면 된다.

 

answer = len(word)

자릿수 길이만큼 answer에 입력해준다. char에 A를 0으로 입력했기 때문에 알파벳이 A만 있는 경우, for문에서 answer는 0을 더하기 때문이다. A만 있는 경우를 A의 개수만큼 더해주어야 한다. 이를 기본값으로 지정해야한다.

입력값 알파벳 원소를 왼쪽부터 한개씩 확인한다.

O일 경우 A,E의 모든 re를 반복하고 세번째 반복이므로, re에 3을 곱해준다.

한 자리를 검사한 경우, (re-1)//5 한 자리에 해당하는 경우의 수를 빼주면서 re를 업데이트한다.

# 정답2
def solution(word):
    char = {'A':0,'E':1,'I':2,'O':3,'U':4}
    answer = len(word)
    re = (((5+1)*5+1)*5+1)*5+1
    for i in word:
        answer += re * char[i]
        re = (re-1)//5
    
    return answer

 

---

레퍼런스

• 정답 참고

(프로그래머스 연습 문제 풀이) 모음 사전

• 깃허브 정답

GitHub - yyeongeun/codingtest: 코딩테스트 공부