문제 84512. 모음사전

문제 링크

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

프로그래머스

 

 

난이도 : Lv.2 

 

문제 요약 설명

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

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

입력

• 단어 하나 word

입력 제한

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

입력 예제

// input
"AAAAE"

// ans
6

 

풀이 방식

해당 문제는 순서의 기준이 조금 까다로워 짜증이 났던 문제 중 하나이다.(그래서 그런지 풀이 방식도 그리 좋은 접근법은 아니다.) 순서가 증가하는 패턴은 다음과 같다

1. 문자열의 길이가 5가 아닌경우, A를 추가한다

  ex) A -> AA -> AAA -> ...

2. 문자열의 길이가 5로 꽉 찬 경우, 가장 오른쪽의 문자가 U가 될 때까지 A -> E -> I -> O -> U 순서로 변경한다.

  ex) AAAAA -> AAAAE -> AAAAI -> ...

3.  가장 오른쪽의 문자가 U라면 올림수 처리를 하고, 올림수 처리가 된 모든 문자들을 전부 삭제한다.

  ex) AUUUU -> E

이 패턴들을 준수하며 코드를 짜면 정답이 된다.

풀이 방식은 브루트 포스로, 정답이 나올때까지 무식하게 While문을 돌리면서 순서를 증가시키며 찾았다. 5개의 모음과 크기가 5인 문자열임으로 5^6의 경우의 수밖에 나오지 않아(공백도 포함이기 때문에 한 자리에 올 수 있는 경우는 총 6가지이다.) 시간초과가 날 수 없기 때문이다.

정답 코드 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(string word) {
    int answer = 0;
    string cur_word = "";
    vector<char> v1 = {'A', 'E', 'I', 'O', 'U'};
    
    for(int i = 0; i < word.length(); i++){
        switch(word[i]){
            case 'A':
                word[i] = '0';
                break;
            case 'E':
                word[i] = '1';
                break;
            case 'I':
                word[i] = '2';
                break;
            case 'O':
                word[i] = '3';
                break;
            case 'U':
                word[i] = '4';
                break;
        }
    }
    
    cout << word << '\n';
    
    while(word != cur_word){
        if(cur_word.length() != 5){
            cur_word += '0';
        }
        else{
            cur_word[4]++;
            
            while(cur_word[cur_word.length()-1] > '4'){
                cur_word[cur_word.length()-2]++;
                cur_word.erase(cur_word.length()-1);
            }
        }
        //cout << cur_word << '\n';
        answer++;
    }

    return answer;
}

 

더 좋은 코드?

아무래도 브루트 포스 방식으로 문제를 풀었기 때문에 알고리즘의 성능이 좋지 않다. 그래서 해당 문제가 완전탐색으로 분류된만큼 DFS나 BFS같은 탐색 방식을 활용할 수 도 있고, 순서가 증가하는 패턴의 이해도를 높여 선형적으로 하나씩 찾는게 아닌, 한 번에 찾는 로직을 짤 수 도 있을 것 같다. 필자는 이 문제에 많은 시간을 투자하기를 원치 않기 때문에 연구를 추가적으로 하지않고 여기서 마무리지으려 한다.