[알고리즘 일기] 142. 위클리 챌린지 5주차_모음사전

 

문제 142. (2021-09-19)

 

문제 출처 | 프로그래머스(Programmers)
언어 | 파이썬(Python)

코딩테스트 연습 - 5주차_모음사전

 

 

문제 설명

위클리 챌린지 5주차_모음사전

 

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

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

 

❧ 제한 사항

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

 

❧ 입출력 예

---

🔑 문제 접근 방법

1. 'A', 'AA', 'AAA', 'AAAA' 를 다섯 자리 숫자로 생각하고

'10,000', '11,000', '11,100', '11,110' 으로 가정하여 대소 관계 표현 시도 ➡ 문자열을 숫자로 표현하는 게 다소 복잡함

✔ 2. 규칙에 따라 문자열 생성 후, 타겟 문자열이 나올 경우 카운트값 반환

 

❧ 풀이

def solution(word):
    alphabet = {0:'A', 1:'E', 2:'I', 3:'O', 4:'U'}
    rev_alphabet = {'A':0, 'E':1, 'I':2, 'O':3, 'U':4}
    cnt = 0
    string = []
    while True:
        cnt += 1
        # 문자열의 개수가 5 미만일 경우, 뒤에 문자를 추가해줌
        if len(string) < 5:
            string.append('A')
        # 맨 뒤 문자가 'U'일 경우, 문자열 표현의 한계에 다다랐으므로 앞의 문자를 한 수준 증가함
        elif string[-1] == 'U':
            while string[-1] == 'U':
                string.pop()
            string[-1] = alphabet[rev_alphabet[string[-1]] + 1]
        else:
            string[-1] = alphabet[rev_alphabet[string[-1]] + 1]
        if string == list(word):
            return cnt

1️⃣ 규칙성 찾는 데에서 시간을 많이 허비함

2️⃣ 시간복잡도 O(n)

• 문제에서 제시된 규칙대로 문자열 생성
• 문자열 생성 횟수만큼 카운트 셈
• 타겟 문자열 찾았을 경우, 카운트 값 반환

3️⃣ 총 문자열의 개수가 5 미만일 경우, 뒤에 문자열이 오는 경우가

해당 문자열 바로 뒤의 문자가 됨

4️⃣ while 문 추가를 못해줬어서 막힘 ➡ 해결 : 맨 뒤 문자가 'U' 일 경우, pop() 반복