프로그래머스 - 모음사전(C++)

오늘의 미들러 문제는 프로그래머스 : 모음사전이다

모음 A, E, I, O, U를 가지고 중복, 순서 상관없이 길이가 1부터 5까지인 문자열을 만들어 순서를 매긴 다음 매개변수로 들어오는 단어가 사전에서 몇 번째 단어인지를 찾아야 하는 문제이다

정리

내가 생각한 방법은 길이도 길지 않고 문자도 적으니 그냥 재귀로 풀어도 될 것 같았다

재귀 함수를 만들어 만들고자 하는 길이와 만들고 있는 문자열을 매개변수로 받는다

재귀 함수 내에서 모음을 사용해 문자열을 늘려가다가 문자열의 길이가 원하는 길이에 도달하면 이를 벡터에 담는다

백트래킹을 위해 문자열에 모음을 추가하고 함수를 호출한 후 모음을 다시 제거해주자

그렇게 모든 문자열을 다 만들었으면 문제에서 요구하는 순서가 사전 순 정렬이랑 똑같기 때문에 일반적인 sort를 해준다

그리고 반복문을 통해 돌아가다가 word를 발견하면 끝

코드

#include <bits/stdc++.h>

using namespace std;

char alpha[5] = {'A', 'E', 'I', 'O', 'U'};
vector<string> dict;

void DFS(int r, string s)
{
    if(s.size() == r)
    {
        dict.push_back(s);
        return;
    }
    
    for(int i = 0; i < 5; i++)
    {
        s.push_back(alpha[i]);
        DFS(r, s);
        s.pop_back();
    }
}

int solution(string word) {
    int answer = 0;
    
    DFS(1, "");
    DFS(2, "");
    DFS(3, "");
    DFS(4, "");
    DFS(5, "");
    
    sort(dict.begin(), dict.end());
    
    for(int i = 0; i < dict.size(); i++)
    {
        if(dict[i] == word)
        {
            answer = i + 1;
            break;
        }
    }
    
    return answer;
}

회고

내가 푼 방법 외 다른 방법을 살펴보았다

• 일반적으로 DFS를 사용하신 분들도 있는데 나처럼 모든 문자열을 만들고 정렬 후 word를 찾는 것이 아니라 그냥 DFS를 돌리며 순서를 증가시키다가 똑같은 단어를 찾으면 그 순서를 바로 정답으로 하더라

  • 이게 더 효율적인 코드같다. 이걸 생각 못했네

• 몇몇 분들은 규칙을 찾아 빠르게 풀었는데 되게 신박했다. A,E,I,O,U를 숫자로 보고 규칙을 찾아 O(L)의 방법으로 풀었다. 이런 생각을 할 수 있는 머리가 부럽다 ㅜ

  • 참고 블로그