99클럽 코테 스터디 16일차 TIL + 완전탐색

오늘의 문제 - 완전탐색

프로그래머스 - 모음사전

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

---

내 풀이 및 접근 방식

1. 중복 순열 라이브러리 사용

파이썬 중복 순열 라이브러리인 product를 이용한 방법!

from itertools import product
def solution(word):
    dic = {}
    dic_words = []
    for i in range(1,6):
        for j in product(['A', 'E', 'I', 'O', 'U'], repeat=i): 
            dic_words.append(''.join(j))
    
    dic_words.sort()
    for i, d in enumerate(dic_words, start=1):
        dic[d] = i
        
    return dic.get(word)

풀이 

1. 중복 순열 라이브러리 product에서 선택 수의 값을 1~5로 바꿔주며 만들 수 있는 단어 경우의 수를 모두 구하였다.
2. 모든 단어들을 사전순으로 정렬한다.
3. dictonary를 이용하여 key값을 단어로 하고, value를 인덱스로 하여 사전에 추가한다.
4. 주어진 word를 key로 하여 인덱스를 조회한다.

---

다른 풀이

1. DFS 이용 풀이

def solution(word):
    answer = 0
    alphaNum = {'cur': 0}
    alphaSet = ['A','E','I','O','U']
    def dfs(found):
        if len(found) > 5:
            return

        if found not in alphaNum:
            alphaNum[found] = alphaNum['cur']
            alphaNum['cur'] += 1

        for s in alphaSet:
            dfs(found+s)
    dfs('')
    answer = alphaNum[word]
    return answer

풀이

1. dfs: 단어 인덱스 사전 구축
   A, E, I, O, U 순서대로 재귀를 통해 이어붙여나가며 단어 사전을 만든다.
   dfs 실행 순서: A->AA->AAA->AAAA->AAAAA->AAAAE->AAAAI ... -> AAAE -> AAAEA -> AAAEE ...
   사전 순으로 dfs가 실행되며 사전에 단어를 추가한다.
2. 주어진 word를 key값으로 인덱스를 반환한다. 

2. 직접 계산법

현재 자리의 알파벳을 통해 앞 순서의 몇개의 단어들이 있는지를 계산하고 이를 더해서 인덱스를 출력한다.

def solution(word):
    answer = 0
    S = ['A','E','I','O','U'] 
    data = 1
    for i in range(4,-1,-1):
        if len(word) > i:
            answer += data * S.index(word[i]) + 1
        data += 5 ** (5-i)
    return answer

 

단어의 길이에 비례하는 시간만 소요되고, 추가적인 메모리 사용이 없기 때문에 시간과 공간 측면에서 앞선 코드들보다 효율적이다. 

---

회고

product 이외에도 반복가능한 객체들 관련한 함수가 여러개 있어서 정리하면 다음과 같다. 쓰일 수 있으니 외우자.

순열: 순서 구분 => permutations(<반복객체>, n)

중복 순열: 순서 구분, 중복 허용 => product(<반복객체>, repeat=n)

조합: 순서 구분하지 않음 => combinations(<반복객체>, n)

중복 조합: 순서 구분하지 않음, 중복 허용 => combinations_with_replacement(<반복객체>, n)

 

n은 반복 객체에서 뽑는 개수이다.