[programmers] 모음사전

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

완전탐색

 

---------------------------------------------------풀이----------------------------------------------------

 

사전 순서를 고려한다고 생각하지 말고, 숫자라고 생각하면 좋을 것 같다.

소숫점을 생각한다면, A = 0.1, AAA = 0.111, AAAU = 0.1115, ... 등 이다.

이 방식대로 A부터 시작해 완전탐색을 통해 몇 번째 문자열인지 구하는 방식이다.

 

알고리즘은 다음과 같다.

빈 문자열 ans를 준비한 뒤, 증가시키면서 이 문자열이 구하고자 하는 문자열에 해당하는 word와 일치하면 그 때의 answer를 리턴한다.

즉, ans를 사전 순서대로 하나씩 다음 문자열로 바꾸어 나가고,

그 때마다 answer를 1 증가시킨다.

만약 word와 일치하면 종료한다.

 

이를 위해 while문을 word와 ans가 같아질 때까지 반복하였다.

우선, ans 맨 뒤에 'A'를 추가한다. ( 소숫점에서 맨 뒤에 1이 붙는 것이 그 다음으로 작은 숫자가 되므로 - 즉, 0.23 다음은 0.231이다.)

그런데 ans의 가능한 최대 길이는 5이므로 그것보다 크면 반올림을 해준다.

예를 들어, AAAAE에서 A를 덧붙이면 AAAAEA가 된다.

그런데 길이가 5를 넘어가므로, 맨 뒤의 A를 삭제한 뒤 carry를 E의 위치에 더해주는 방식이다.

E 다음은 I이므로 AAAAEI가 된다.

이와같은 방식으로 맨 뒤 문자는 삭제하고, carry를 바로 위 자릿수에 더해 문자를 바꿔준다.

그런데, 제일 큰 문자인 U는 다음 문자가 없으므로 U에서 반올림 될 경우 다시 carry가 발생한다.

이 케이스는 결국, 다시 U가 위치했던 자릿수부터 carry를 올려주는 것이 반복되는 상황이다.

따라서 다른 문자들(A, E, I, O)의 경우, carry가 발생하면 그 다음 문자로 옮겨주기만 하면 되지만,(A->E->I->O->U)

U의 경우, 이 문자의 위치에서 다시 carry가 발생해 그 위로 carry를 올려줘야 한다.

예를 들면, AAAAU에서 A를 뒤에 추가해 AAAAUA가 되는데,

5자리 이상이므로 마지막 A를 삭제하고 AAAAU에서 U에 carry를 더해준다.

그런데 U 다음 문자는 없으므로 다시 이 과정을 반복한다.

따라서 AAAAU에서 맨 뒤의 U를 삭제하고, 마지막 A에 carry를 더해 AAAAU->AAAA->AAAE로 변경되는 것이다.

 

정리하면,

1. ans의 마지막에 A를 추가한다.

2. 길이가 5보다 크면 뒤에서부터 반올림한다.

2.1. 맨 뒤의 문자를 삭제한다.

2.2. A면 E, E면 I, E면 O, O면 U로 바꿔주고 종료한다.

2.3. U면 2.1부터 다시 반복한다.

이 과정을 ans가 word와 같아질 때까지 반복한다.

#include <string>
#include <vector>

using namespace std;

// A AA AAA AAAA AAAAA AAAAE AAAAI AAAAO AAAAU AAAE AAAEA 
int solution(string word) {
    int answer = 0;
    string ans = "";
    while(word != ans){
        // ans를 다음 단어로 옮김 => 뒤에서부터 확인
        // 1. 뒤에 A를 추가
        ans += 'A';
        // 2. 길이가 5보다 크면 뒤에서부터 반올림
        if(ans.length() > 5){
            int i = 5;
            while(i--){
                // 뒷부분 길이 넘는 문자 제거
                ans.erase(ans.begin() + i+1);
                if(ans[i] == 'A'){
                    ans[i] = 'E';
                }
                else if(ans[i] == 'E'){
                    ans[i] = 'I';
                }
                else if(ans[i] == 'I'){
                    ans[i] = 'O';
                }
                else if(ans[i] == 'O'){
                    ans[i] = 'U';
                }
                // 반올림 후 위로 carry가 생기는 경우
                else if(ans[i] == 'U'){
                    // 다음 문자에 대해 한 번 더 해야함.
                    continue;
                }
                // carry가 없을 경우 종료.
                break;
            }
        }
        answer++;
    }
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

완전탐색 문제라고 생각하면 매우 간단했던 문제이다.