프로그래머스 - 모음 사전

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

Link

문제

사전에 알파벳 모음 ‘A’, ‘E’, ‘I’, ‘O’, ‘U’만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 “A”이고, 그다음은 “AA”이며, 마지막 단어는 “UUUUU”입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• word의 길이는 1 이상 5 이하입니다.
• word는 알파벳 대문자 ‘A’, ‘E’, ‘I’, ‘O’, ‘U’로만 이루어져 있습니다.

입출력 예

word	result
"AAAAE"	6
"AAAE"	10
"I"	1563
"EIO"	1189

풀이

문제의 목적은 단어가 주어졌을 때 몇번째 단어인지를 Return하는 것…

문제를 본 순간 몇가지 해결방법들이 떠올랐다.

• 바이너리 트리 구조로 만들어서 Depth first search로 해당 단어를 찾아갔을 때의 count
• 중복순열을 사용해서 풀기
• 단어의 순서가 결정되는 규칙을 찾기

중복순열은 중복을 허용하는 순열을 의미한다. 예를들어 [‘E’, ‘A’]와 [‘A’, ‘E’]는 성분이 서로 같아 순열의 경우 하나로 취급되지만 중복순열은 각각이 다른 케이스로 취급된다.

중복순열로 할 것은 모든 단어가 순서대로 적힌 사전을 만드는 것인데, 이 사전에는 EA와 AE 둘다 있어야하기 때문에 중복순열을 쓰는 것이 옳다.

itertools 라이브러리의 product함수는 리스트와 repeat이라는 인자를 받아 리스트로 repeat의 길이의 중복순열을 만들어준다.

이를 활용하여 코드를 작성하면 아래와 같다.

from itertools import product
def solution(word):
    answer = 0
    c_list = ['A', 'E', 'I', 'O', 'U']
    dic = []
    for i in range(1, 5+1):
        # 단어의 길이를 조절
        w_len = i
        prod = list(product(c_list, repeat=i))
        # 순복순열 케이스를 하나씩 꺼내 단어로 다시 조합
        for case in prod:
            temp = ''
            for c in case:
                temp += c
            dic.append(temp)
    # 정렬한 뒤 거기서 index를 찾아 +1을 하여 반환
    return sorted(dic).index(word) + 1

다음은 단어의 순서 규칙을 찾아보자.

AAAA는 4번째 단어이다.

AAAAA는 5번째 단어이다.

그렇다면 AAAAE는? 6번째 단어이다.

그렇다면 AAAAU는? 9번째 단어이다.

그렇다면 AAAE는? 10번째 단어이다.

여기까지보면 AAAAA가 AAAAE가 되는것, 즉 5번째 알파벳이 다음 알파벳으로 넘어가는것은 1의 차이가 나게된다.

AAAA가 AAAE가 되는거에는 6의 차이가 난다.

그럼 AAA는 3번째 단어일 때, AAE는 몇번째 단어일까?

일단 AAAE가 AAAU가 되면 AAAU의 순서는 10 + 18 = 28이되고

그럼 AAE는 그 다음 수니까 29이다.

AAA와 AAE는 26의 차이가 나니까 위의 패턴과 비교해보면 자리수에 따라 알파벳이 변하는데에는 1+1, 5+1, 25+1씩의 차이가 있다는걸 알 수 있다.

이 규칙을 활용하여 아래와 같이 코딩하면 된다 (코드는 다른 사람거를 참고했다.).

from itertools import product
def solution(word):
    answer = len(word)
    dic = {'A':0, 'E':1, 'I':2, 'O':3, 'U':4}
    k = (((5+1)*5+1)*5+1)*5+1
    for c in word:
        value = dic[c] * k 
        answer += value
        k = (k -1) // 5
    return answer