프로그래머스 코딩테스트 고득점 Kit -
완전탐색
- Lv 2. 모음사전 (Python)
https://school.programmers.co.kr/learn/courses/30/lessons/84512
Code
## 1. product로 모든 조합 구해서 인덱스 찾기 (구질구질 방법)
from itertools import product
def solution(word):
answer = 0
alphabet = ['A', 'E', 'I', 'O', 'U']
product_list = []
dictionary = []
for i in range(1, len(alphabet)+1):
product_list.append(list(product(alphabet, repeat = i)))
tmp = list(product(alphabet, repeat = i))
for j in range(len(tmp)):
make_word = ''
for t in range(len(tmp[j])):
make_word += tmp[j][t]
dictionary.append(make_word)
answer = sorted(dictionary).index(word) + 1
return answer## 2. DFS로 길이 5 이하의 단어를 순서대로 만들어가면서 인덱스 찾기
answer = 0
def solution(word):
alphabet = ['A', 'E', 'I', 'O', 'U']
ans = []
def dfs(cnt, w):
global answer
if (cnt == 5):
return
for i in range(len(alphabet)):
made_word = w + alphabet[i]
if(made_word == word):
answer = len(ans) + 1
ans.append(made_word)
dfs(cnt+1, made_word)
dfs(0, "")
return answer풀이 및 해설
- 설마 ? 하고
product를 썼는데 풀렸다. 그치만 마음에 안듦 너무 안멋져요 - 뭔가
DFS나 백트랙킹으로도 풀 수 있을거같아서 찾아봤는데 의외로DFS로 푼 사람들이 많았다 ! !DFS로 재도전 DFS알고리즘 순서made_word에 현재 있는 단어 + 그 다음 순서 알파벳 를 조합해서 단어 만들어주고 저장- 만약에
made_word가 찾는 단어랑 똑같으면 해당 인덱스answer값에 저장 ans에 A, AA, AAA 처럼 순서대로 넣으면서 돌기cnt = 5일 때return으로 탈출 → 나와서는 그 다음 순서부터 AAAAE, AAAAI, AAAAO, AAAAU를 넣으면서 돌기- 또 5번 다 넣으면
return으로 탈출 → 그 다음 순서인 AAAE, AAAEA, AAAEI … 넣으면서 돌기
What I learned
- 더 깔끔한 product 사용 코드
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()
return words.index(word) + 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참고한 코드
데굴데굴 뚝딱뚝딱 개발기록