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

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

주어진 문자 A, E, I, O, U를 사전순으로 나열했을 때, 문자열 words가 몇 번째 단어인지 구하는 문제이다.

중복을 허용하여 최대 5글자까지 나열하면 되므로 모든 경우의 수를 탐색하여도 시간초과가 발생하지 않는다.

 

중복 순열은 백트래킹(재귀)를 활용하면 쉽게 구현할 수 있다.

아래의 코드에서 func(k)는 k번째 자리를 채우는 함수로, 각각의 자리를 채울 때마다 cnt를 1 증가시키고 문자열이 word와 같을 때 cnt를 기록하여 리턴한다.

 

 

코드

 

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int ans, cnt;
char arr[10];

void func(int k, const string& word) {

    string s = "";
    for (int i=0; i<k; i++)
        s += arr[i];

    if (s == word) ans = cnt;
    if (k >= 5) return;

    for (int i=0; i<5; i++) {
        arr[k] = "AEIOU"[i];
        cnt++;
        func(k+1, word);
    }
}

int solution(string word) {

    func(0, word);
    return ans;
}