[99클럽/코딩테스트 챌린지/C++] 사전에서 특정 단어의 순서 찾기 (모음 사전 문제)

오늘은 모음으로만 이루어진 사전에서 특정 단어가 몇 번째 위치에 있는지 찾는 문제를 해결했습니다. 이 문제는 주어진 단어의 길이가 5 이하이므로, 가능한 모든 조합을 순서대로 생성하며 탐색하는 방식으로 풀 수 있었습니다.

문제링크 : 

https://school.programmers.co.kr/learn/courses/30/lessons/84512?language=cpp

프로그래머스

나의 문제 접근 과정

1, 완전 탐색으로 접근

주어진 단어의 길이가 5 이하이므로, A, E, I, O, U의 가능한 모든 조합을 생성하고, 이를 하나씩 사전 순서대로 생성하여 주어진 단어와 비교하는 완전 탐색 방식으로 접근했습니다.

2, 중첩 반복문을 통한 모든 조합 생성

5개까지의 자리수로 구성된 조합을 각 자리마다 가능한 모음들을 배치하여 만들었습니다. 예를 들어, 첫 번째 자리에서 A부터 U까지 순차적으로 고정한 뒤, 두 번째 자리로 넘어가면서 다시 A부터 U까지 가능한 모든 조합을 생성하는 방식입니다.

3, 조건에 맞는 단어 발견 시 탐색 종료

생성된 조합이 주어진 word와 일치하면 순서를 반환하고 탐색을 종료하도록 했습니다. 단어를 찾지 못한 경우에는 다음 조합을 생성하며 비교를 이어갔습니다.

코드 풀이

아래는 문제 해결을 위한 최종 코드입니다:

#include <string>
#include <vector>

using namespace std;

bool isSame(string &a, string &b)
{
    return a == b;
}
int Find(vector<char> &mo, string &word)
{
    int count = 0;
    string temp = "";
    for (int a = 0; a < mo.size(); a++)
    {
        count++;
        temp = {mo[a]};
        if (isSame(temp, word))
        {
            return count;
        }
        for (int b = 0; b < mo.size(); b++)
        {
            count++;
            temp = {mo[a], mo[b]};
            if (isSame(temp, word))
            {
                return count;
            }
            for (int c = 0; c < mo.size(); c++)
            {
                count++;
                temp = {mo[a], mo[b], mo[c]};
                if (isSame(temp, word))
                {
                    return count;
                }
                for (int d = 0; d < mo.size(); d++)
                {
                    count++;
                    temp = {mo[a], mo[b], mo[c], mo[d]};
                    if (isSame(temp, word))
                    {
                        return count;
                    }
                    for (int e = 0; e < mo.size(); e++)
                    {
                        count++;
                        temp = {mo[a], mo[b], mo[c], mo[d],mo[e]};
                        if (isSame(temp, word))
                        {
                            return count;
                        }
                    }
                }
            }
        }
    }
    return 0;
}


int solution(string word) {
    int answer = 0;
    vector<char> mo = {'A', 'E', 'I', 'O', 'U'};
    answer = Find(mo,word);
    return answer;
}

위 코드의 문제 접근 방법

위의 내 코드는 완전 탐색으로 문제를 해결합니다. A, E, I, O, U를 사용하여 가능한 모든 조합을 만들고, word와 같은 단어가 생성되었을 때 현재 조합의 순서를 반환하여 문제를 해결하는 방식입니다. 하지만 완전 탐색 방식은 반복과 중복 계산이 많고 비효율적이라는 단점이 있습니다.

다른 사람 풀이 (수학적 규칙을 적용한 효율적 풀이)

#include <string>

using namespace std;

int solution(string word) {
    string v = string("AEIOU");
    int a = word.size();

    for(int i = 0, b = 1; i < word.size(); i++, b *= 5)
        a += v.rfind(word[i]) * 781 / b;

    return a;
}

수학적 규칙 설명

1, 고유한 위치 계산

• 각 자리의 문자는 A, E, I, O, U 순으로 사전에서의 위치가 고정됩니다. 따라서 특정 자리의 문자가 word[i]일 때, 이를 기준으로 몇 번째 위치인지를 계산할 수 있습니다.
• v.rfind(word[i])로 word[i]가 AEIOU에서 몇 번째 인덱스인지 구합니다.

2, 자리수에 따른 순서 증가

• 자릿수가 클수록 더 많은 경우의 수가 발생하는데, 각 자릿수의 단어들은 해당 자릿수가 고정될 때 나머지 자리에서 781개의 조합이 생기는 규칙을 사용합니다.
• 각 자리에서 가능한 조합 수는 오른쪽에서 왼쪽으로 자리 수마다 781, 156, 31, 6, 1로 분배되며, 이 값들은 각각 오른쪽 자릿수에서 모든 경우의 수를 커버하는 배율입니다.

3, 순서 계산

• 예를 들어 AEIOU를 기준으로 E는 첫 번째 자리에 781가지의 경우가 존재하므로, 첫 자리에서 E가 있을 때 (1 * 781)만큼을 더하여 해당 자릿수에서 발생하는 모든 경우의 수를 순서에 반영합니다.
• 이를 통해 각 자릿수에 대한 경우의 수가 빠르게 계산되며, 전체 단어의 순서가 효율적으로 계산됩니다.

배운 점

1, 완전 탐색의 한계와 효율적 계산의 중요성

• 완전 탐색은 모든 조합을 시뮬레이션하는 단순한 방식이지만, 중복 연산이 많아 큰 데이터에 비효율적입니다. 반면, 규칙성을 활용한 계산 방식은 연산 횟수를 크게 줄여 성능을 향상시킬 수 있음을 깨달았습니다.

2, 수학적 규칙을 통한 효율성 극대화

• 고정된 순서와 자리마다 조합이 일정한 규칙을 갖는 문제에서는, 수학적으로 계산해 필요한 값만 빠르게 구하는 방식이 더 효율적임을 알게 되었습니다.

3, 자리수마다 고유 배율 적용하기

• 자리수가 증가할수록 가능한 조합이 많아지는 경우, 각 자릿수의 고유 배율을 적용하는 방식으로 전체 조합의 순서를 빠르게 구할 수 있다는 것을 배웠습니다.

결론

이번 문제를 통해 수학적 규칙을 파악하여 문제를 해결하는 방식을 익힐 수 있었습니다. 앞으로는 완전 탐색 방식 외에도 규칙을 찾아 계산 횟수를 줄이는 접근을 시도해야겠다는 점을 느꼈습니다.