문제

Programmers, 모음사전

핵심

• 입력의 크기가 $5$이라 구현에 초점을 맞춘다.
• 모음(A, E, I, O, U)으로 이루어진 단어의 순위를 구하는 문제이다. 예시를 이해하고 규칙을 찾아내는 과정이 조금 까다로웠다. 규칙을 알면 구현은 굉장히 쉽기 때문에 예시를 제대로 이해하고 규칙을 찾도록 하자.
• 1 ~ 10까지 순위가 예시로 나온다. 11을 AAAI로 착각할 수 있는데 AAAE(10)보다 사전 순으로 작은 문자열을 만들 수 있으므로 11은 AAAEA다.

RANK
A		1
AA		2
AAA		3
AAAA	4

AAAAA	5
AAAAE	6
AAAAI   7
AAAAO   8
AAAAU   9

AAAE    10

AAAEA	11
AAAEE	12
AAAEI	13
AAAEO	14
AAAEU	15

AAAI	16
...

• 예시를 보면 단어 길이가 하나 늘어날 때마다 단어 순위가 하나씩 증가한다. "AAAAE"를 보면 단어의 길이가 5이므로 최소 5번째이고, 마지막 E는 A다음에 위치하기에 순위를 하나 올려 "AAAAE"는 6번째에 위치한다.
• "E" 단어는 모음사전에서 몇 번째로 위치할까? "A * * * * "로 시작하는 것보다 앞에 있을 것이다. 그렇다면 A로 시작하는 단어의 개수를 찾아보자. A로 시작하는 단어는 5글자, 4글자, 3글자, 2글자, 1글자가 있을 것이다. A로 시작하는 단어의 5글자 가짓수는 나머지 4글자에 대해 A, B, C, D, E가 가능하므로 가능한 경우의 수는 $5^4$으로 볼 수 있다. A로 시작하는 단어의 4글자 가짓수는 나머지 3글자에 대해 A, B, C, D, E가 가능하므로 $5^3$으로 볼 수 있다. ... A로 시작하는 단어의 1글자는 A 하나가 존재한다. 즉, $5^4 + 5^3 + 5^2 + 5^1 + 1 = 781$개 뒤에 있으며, 단어 길이가 하나이므로 782번째 단어가 된다.
• 마찬가지로 "EIO" 단어는 모음 사전에서 몇 번째로 위치할 지 생각해보자. "E * * * * " 보다 뒤에 있으니 781(625 + 125 + 25 + 5 + 1)을 더한다. "EA * * * "보다 뒤에 있으니 156(125 + 25 + 5 + 1)을 더한다. "EI * * * "보다 뒤에 있으니 151을 더한다. "EAA * * " 보다 뒤에 있으므로 31(25 + 5 + 1)을 더한다. 이를 EAE(31), EAI(31) 보다 뒤에 있으므로 이를 다 더하면 1186이 된다. 단어 길이가 3개 이므로 1189번째 숫자가 된다.
• 그렇다면 규칙을 찾을 수 있다. 5개의 문자에서 자릿수에 해당하는 가중치(offset)을 부여할 수 있다. 가중치는 위의 계산 식을 토대로 {781, 156, 31, 6, 1}이 된다. 이 가중치를 토대로 해당 단어보다 앞에 있는 단어의 개수를 효율적으로 파악할 수 있다.

개선

코드

시간복잡도

• $O(N)$

C++

#include <string>
#include <vector>
#include <iostream>

using namespace std;
int solution(string word) {
    int score[5] = {};
    int idx = 0;
    for (auto c : word) {
        if (c == 'A') score[idx] = 0;
        else if (c == 'E') score[idx] = 1;
        else if (c == 'I') score[idx] = 2;
        else if (c == 'O') score[idx] = 3;
        else score[idx] = 4;
        ++idx;
    }
    int w[5] = {781, 156, 31, 6, 1};
    int ans = word.length();
    for (int i = 0; i < 5; ++i)
        ans += w[i] * score[i];
    return ans;
}

Java

class Solution {
    public int solution(String word) {
        int[] score = {0, 0, 0, 0, 0};
        int idx = 0;
        for (var c : word.toCharArray()) {
            if (c == 'A') score[idx] = 0;
            else if (c == 'E') score[idx] = 1;
            else if (c == 'I') score[idx] = 2;
            else if (c == 'O') score[idx] = 3;
            else score[idx] = 4;
            ++idx;
        }
        int[] w = {781, 156, 31, 6, 1};
        int ans = word.length();
        for (int i = 0; i < 5; ++i)
            ans += w[i] * score[i];
        return ans;
    }
}