[프로그래머스] 모음 사전. 다양한 python 풀이

내 코드

import heapq
def solution(word):
    D=[]
    def make(str1):
        if(str1!=''):
            heapq.heappush(D,str1)
        if(len(str1)==5): return
        for c in 'AEIOU':
            make(str1+c)
    make('')
    cnt=1
    while(D[0]!=word):
        heapq.heappop(D)
        cnt+=1
    return cnt

• 재귀로 문자열을 만들었다.
• 정렬을 해야하는데 O(NogN) 이 걸릴걸 우려해, 생성하면서 heap에 넣었다.
• heap에 넣는것도 O(logN)을 N 번 하므로 O(NlogN)이지만, 생성하면서 바로 넣으면 두번 일을 하지 않아도 되지 않을까? 하는 생각에서였다. 하지만 틀린 생각이였다.

고찰

• heap에 넣는 경우:
  • 넣을 때 (heappush): O(NlogN)
  • 찾을 때 (heappop) : 최악의 경우 O(NlogN)
  • 총 시간 복잡도 : O(NlogN)
• 단순히 넣고, 정렬 후 index로 찾는 경우
  • 넣을 때: O(N)
  • 정렬: O(NlogN)
  • 찾을 때 O(N)
  • 총 시간 복잡도: O(NlogN)
• 시간 복잡도는 같지만, 그 안의 로직을 보면 heap이 좀더 오래 걸리고, heap구조를 만드는데 오버헤드도 있어 더 오래 걸릴 것 같다.

다른 사람 코드

수학으로 풀기

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

• 문자열을 직접 만들지 않고, 해당 문자열이 몇번째에 위치할지 수학적으로 계산하는 코드다.

해설

• “A” 는 맨 처음에 온다. “AA”는 그 다음에 온다. 그다음 “AAA” …
• “E”라는 글자는 따라서 A로 시작하는 모든 조합 뒤에 온다.
  • 식으로 나타내면 1+5+5*5.. 이런식으로 간다. (순서가 어떻게 오건 숫자만 세면 된다.)
  • c(패턴) 이 패턴을 세는 함수라고 했을 때, c(A) + c(A*) + c(A**) + .. = 1 + 5 + 5*5 .. 이기 때문이다. ( 문자에서 *기호를 AEIOU중 한글자가 오는 패턴이라 했을 때)
  • 일반화 시키면 5^0 + 5^1 + 5^2 + 5^3 + 5^4 + 5^5 인데, 등비수열의 합이므로 공식 (r^n-1)/(r-1) 을 이용하여 (5^5-1) /(5-1) 로 표현할 수 있다.
• 두번째 글자에 대해서도 마찬가지 공식을 적용할 수 있다.
  • 그 식이 (5 ^ (5-i) -1)/(5-1) 이다.
  • 예를 들어 ‘O’ 의 경우, 앞에 E,I,O가 오는 모든 경우가 앞에 위치할 것이므로 해당 조합의 수만큼 더해야 한다.
  • 이를 곱하기로 처리한 것이 * “AEIOU”.index(n) 이다.
• 자기 자신도 세줘야, 뒷 문자가 그 순서에 더해나갈 것이기 때문에 +1 을 해준다.

Product

https://docs.python.org/ko/3/library/itertools.html#itertools.product

from itertools import product

solution = lambda word: sorted(["".join(c) for i in range(5) for c in product("AEIOU", repeat=i+1)]).index(word) + 1

• product를 이용해 조합을 생성한 코드다.
• product(A,B) 를 하면 A와B의 데카르트 곱(Cartesian product)이 생긴다.
  • 데카르트 곱은 만들 수 있는 모든 조합이다.
  • (x,y),(a,b,c)를 데카르트 곱하면 ((x,a),(x,b),(x,c),(y,a),(y,b),(y,c))이다.
  • 참고로 ‘르네 데카르트’의 라틴어 이름이 ‘Renatus Cartesius’ 라고 한다.
• product(A, repeat=3)은 product(A,A,A) 와 같다.

제너레이터이션

• 실제 문자 순서대로 생성을 해나가는 코드도 있다.

def solution(word, cnt=1):
    w={'A':'E','E':'I','I':'O','O':'U','U':0}
    def nxt(i):
        return i[:-1]+w[i[-1]] if w[i[-1]] else nxt(i[:-1])
    i='A'
    while i!=word:
        if len(i)<5:
            i+='A'
        elif i[-1]:
            i=nxt(i)
        cnt += 1
    return cnt

• 진짜 제너레이터로 풀면 다음과 같이 풀 수 있다.

def generate_combinations():
    sequence = ['A']
    
    while True:
        yield ''.join(sequence) 
        
        if len(sequence) < 5:
            sequence.append('A') 
        else:
            for i in range(4, -1, -1):
                if sequence[i] != 'U':
                    next_char_index = 'AEIOU'.index(sequence[i]) + 1
                    sequence[i] = 'AEIOU'[next_char_index]
                    sequence = sequence[:i+1] 
                    break
                if i == 0:
                    return
                sequence[i] = 'A'

def solution(word):
    cnt = 1
    for combo in generate_combinations():
        if combo == word:
            return cnt
        cnt += 1

dfs 제너레이션

• 정의대로 깊이 탐색을 하는 코드도 있었는데, 중간에 문자를 만나면 return하게 수정하여 좀더 효율적으로 만들 수 있다.

def solution(word):
    alphaSet = 'AEIOU'
    count = [-1]
    def dfs(current):
        
        if len(current) > 5: 
            return False
        
        count[0] += 1
        
        if current == word:
            return True
        
        for s in alphaSet:
            if dfs(current + s):
                return True
        return False

    dfs('')
    return count[0]

캐싱

• 쌩으로 모든 문자를 집어넣은 코드
• 각각의 조합의 수까지만 하드코딩으로 집어넣은 코드

마무리

• 프로그래머스는 속도 비교를 하기는 어렵지만, 비슷한 풀이를 모아버려서 여러 풀이를 탐색하기가 편한 것 같다.
• 포스팅 하니까 정리가 더 잘되는 것 같고 좋다!