[C++] 프로그래머스 모음사전

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

코딩테스트 연습 - 모음사전

 

1. 서론

 

처음에는 문자를 생성하는 규칙을 어떻게 구현해야 하는가 때문에 막혔는데 그냥 경우의 수로 생성하고 사전 순으로 정렬하는 방법이 나중에 떠올라서 풀게 된 문제. 그런데 다른 사람들은 어떻게 풀었나 보니까 문자 생성 규칙을 이해하고 그걸 코드로 구현해서 풀었더라... 진짜 다들 사고력이 좋은 듯 ㅠ

 

2. 문제 풀이

 

A, E, I, O, U 만을 사용해서 만들 수 있는 단어가 적혀있는 사전이 있다. 그 사전에서 주어진 word가 몇 번째 단어인가를 구하는 문제이다.

첫 번째 단어는 A, 두 번째 단어는 AA.. 마지막 단어는 UUUUU 라고 한다.

 

이것만 가지고는 어떤 규칙으로 단어가 만들어지는지 모르겠어서 입출력 예시를 봤다. 근데 입출력 예시를 봐도 어떤 논리구조로 단어가 생기는지 모르겠어서 이걸 어떻게 구현하지 고민하다가 모르겠어서 덮어뒀다 다시 보니까 그냥 다섯 개의 문자들을 이용해서 문자열이의 길이가 1~5인 조합을 만들어서 사전 순으로 정렬하면 되겠다는 생각이 떠올랐다.

 

A, E, I, O, U 이 문자를 가지고 중복조합을 이용해서 문제를 풀었다. 중복 조합으로 단어를 만들어내서 배열에 넣고 배열을 정렬한 후에 배열에서 word를 찾아서 index를 찾아내 return 했다.

 

 

 

 

중복 조합 코드 출처:

https://ansohxxn.github.io/algorithm/repeated-combination/

(C++) 중복 조합(Repeated Combination) 구현하기

 

 

3. 코드 설명

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> v;

void combination(vector<char> a, vector<char> comb, int idx, int d)
{
    if (d == comb.size())
    {
        string s = "";
        for (int i = 0; i < comb.size(); i++)
            s += comb[i];
        v.push_back(s);
        return;
    }
    else
    {
        for (int i = idx; i < a.size(); i++)
        {
            comb[d] = a[i];
            combination(a, comb, idx, d + 1);
        }  
            
    }
}

int solution(string word) {
    int answer = 0;
    vector<char> c = {'A', 'E', 'I', 'O', 'U'};
    
    for (int i = 1; i <= 5; i++)
    {
        int r = i;
        vector<char> comb(r);
        
        combination(c, comb, 0, 0);
    }
    
    sort(v.begin(), v.end());
    answer = find(v.begin(), v.end(), word) - v.begin() + 1;
    
    return answer;
}

 

combination 메소드에서 중복 조합으로 문자열을 만든다. 만들어진 문자열은 벡터 v에 저장한다. 중복 조합은 각자 1자리 ~ 5자리의 단어의 조합을 만들어야 하기 때문에 문자열 반복문으로 1 ~ 5 숫자를 지정해서 조합을 만들어준다.

조합들이 전부 v에 저장되면 배열을 정렬하고 find() 함수를 사용해서 word가 있는 index를 찾아준다.

* find 함수를 사용할 때 - v.begin()을 해줘야 index 값을 구할 수 있다. (쓸 때마다 까먹어서 매번 찾아보는 듯 ㅎ)

그리고 컴퓨터는 0번부터 시작하니까 + 1로 값을 맞춰줬다.