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

모음사전

문제 링크

모음사전

분석

‘A’, ‘E’, ‘I’, ‘O’, ‘U’로 5개의 단어가 있을 수 있으므로 가중치는, 자릿 수만큼 5를 곱하면 됩니다.

첫 번째 자리 $5^4 + 5^3 + 5^2 + 5^1 + 5^0(1) = 781$
두 번째 자리 $5^3 + 5^2 + 5^1 + 5^0(1) = 156$
세 번째 자리 $5^2 + 5^1 + 5^0(1) = 31$
네 번째 자리 $5^1 + 5^0(1) = 6$
다섯 번째 자리 $5^0(1)$

각 자리에서 모음이 몇 번째인지 구하고 앞에 글자 개수를 곱해주어야 합니다.
A(1번째), E(2번째), I(3번째), O(4번째), U(5번째)

예를 들어, "AAAAE"의 경우 다음과 같습니다.

A는 1번째로 $(1 - 1) \times 781 + 1 = 1$
A는 1번째로 $(1 - 1) \times 156 + 1 = 1$
A는 1번째로 $(1 - 1) \times 31 + 1 = 1$
A는 1번째로 $(1 - 1) \times 6 + 1 = 1$
E는 2번째로 $(2 - 1) \times 1 + 1 = 2$
$1 + 1 + 1 + 1 + 2 = 6$

$(1 - 1)$을 해주는 이유는 건너 뛰어야 할 모음의 수를 계산하기 위해서입니다.
예를 들어, A는 첫 번째 모음으로 건너뛸 필요가 없습니다.
E는 두 번째 모음으로 A를 건너뛰어야 하며, $(2 - 1)$의 값이 건너뛰어야 할 모음 수입니다.

예를 들어, "AAAE"의 경우 다음과 같습니다.

A는 1번째로 $(1 - 1) \times 781 + 1 = 1$
A는 1번째로 $(1 - 1) \times 156 + 1 = 1$
A는 1번째로 $(1 - 1) \times 31 + 1 = 1$
E는 2번째로 $(2 - 1) \times 6 + 1 = 7$
$1 + 1 + 1 + 7 = 10$

예를 들어, "I"의 경우 다음과 같습니다.

I는 3번째로 $(3 - 1) \times 781 + 1 = 1563$

예를 들어, "EIO"의 경우 다음과 같습니다.

E는 2번째로 $(2 - 1) \times 781 + 1 = 782$
I는 3번째로 $(3 - 1) \times 156 + 1 = 313$
O는 4번째로 $(4 - 1) \times 31 + 1 = 94$
$782 + 313 + 94 = 1189$

풀이

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(string word) {
    int answer = 0;
    
    // 모음의 인덱스
    unordered_map<char, int> vowelIndex = {{'A', 0}, {'E', 1}, {'I', 2}, {'O', 3}, {'U', 4}}; 
    // 가중치
    vector<int> jump = {781, 156, 31, 6, 1};
    
    for (int i = 0; i < word.size(); i++)
    {
        answer += vowelIndex[word[i]] * jump[i] + 1;
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(1)$입니다.

• word를 순회하는 반복문의 최대 횟수는 5회 $O(5 \approx 1)$

공간 복잡도는 $O(1)$입니다.

• 5개의 문자를 저장하는 vowelIndex $O(5 \approx 1)$
• 5개의 정수를 저장하는 jump $O(5 \approx 1)$
• $O(1 + 1)$

테스트 1 〉 통과 (0.01ms, 4.13MB)
테스트 2 〉 통과 (0.02ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 4.2MB)
테스트 4 〉 통과 (0.01ms, 4.14MB)
테스트 5 〉 통과 (0.01ms, 4.2MB)
테스트 6 〉 통과 (0.02ms, 3.67MB)
테스트 7 〉 통과 (0.02ms, 4.2MB)
테스트 8 〉 통과 (0.01ms, 4.14MB)
테스트 9 〉 통과 (0.01ms, 4.2MB)
테스트 10 〉 통과 (0.01ms, 4.01MB)
테스트 11 〉 통과 (0.01ms, 4.14MB)
테스트 12 〉 통과 (0.01ms, 3.67MB)
테스트 13 〉 통과 (0.01ms, 4.21MB)
테스트 14 〉 통과 (0.01ms, 4.14MB)
테스트 15 〉 통과 (0.01ms, 3.63MB)
테스트 16 〉 통과 (0.01ms, 4.21MB)
테스트 17 〉 통과 (0.01ms, 4.21MB)
테스트 18 〉 통과 (0.01ms, 4.21MB)
테스트 19 〉 통과 (0.01ms, 4.14MB)
테스트 20 〉 통과 (0.01ms, 4.16MB)
테스트 21 〉 통과 (0.01ms, 4.2MB)
테스트 22 〉 통과 (0.01ms, 4.13MB)
테스트 23 〉 통과 (0.01ms, 4.15MB)
테스트 24 〉 통과 (0.01ms, 4.21MB)
테스트 25 〉 통과 (0.01ms, 4.14MB)
테스트 26 〉 통과 (0.01ms, 4.14MB)
테스트 27 〉 통과 (0.01ms, 4.21MB)
테스트 28 〉 통과 (0.01ms, 4.14MB)
테스트 29 〉 통과 (0.01ms, 3.65MB)
테스트 30 〉 통과 (0.01ms, 4.16MB)
테스트 31 〉 통과 (0.01ms, 4.21MB)
테스트 32 〉 통과 (0.01ms, 4.21MB)
테스트 33 〉 통과 (0.01ms, 3.68MB)
테스트 34 〉 통과 (0.01ms, 3.73MB)
테스트 35 〉 통과 (0.01ms, 4.13MB)
테스트 36 〉 통과 (0.01ms, 4.22MB)
테스트 37 〉 통과 (0.01ms, 4.13MB)
테스트 38 〉 통과 (0.01ms, 4MB)
테스트 39 〉 통과 (0.01ms, 3.68MB)
테스트 40 〉 통과 (0.01ms, 4.13MB)