알고리즘(C++) / 프로그래머스 위클리 챌린지 : 5주차 모음

위클리 챌린지 : 5주차 모음 사전

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

코딩테스트 연습 - 5주차

 

코드

//프로그래머스 위클리 챌린지 모음 사전
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int solution(string word) {
    int answer = 0;

    answer += word.size();
    for (int i = 0; i < word.size(); i++) {
        int sum = 0;
        int five = 1;
        int n = 0;
        if (word[i] == 'E') n = 1;
        else if (word[i] == 'I') n = 2;
        else if (word[i] == 'O') n = 3;
        else if (word[i] == 'U') n = 4;

        for (int j = 0; j < 5 - i; j++) {
            sum += five;
            five *= 5;
        }
        answer += (sum * n);
    }

    return answer;
}

int main() {
    string word = "AAE";
    cout << solution(word) << "\n";
    return 0;
}

 

설명

AAAAA                                              5
AAAAE                                 5+1x1 = 6
AAAE                           4+(1+5)x1 = 10
AAE                        3+(1+5+25)x1 = 34
AE                  2+(1+5+25+125)x1 = 158
I             1+(1+5+25+125+625)x2 = 1563

다음과 같은 규칙을 가진다.

word의 사이즈만큼 더해주고 word자리에서 알파벳자리수를 곱한 만큼 더해준다.

(첫 번째 자리 : (1+5+25+125+625), 두 번째 자리 : (1+5+25+125),...)

 

예를 들어 AAE는 3+(1+5+25) x1 = 34이다.

AAE 전에 올 수 있는 단어는 한자리 "A"(1), 두 자리 "AA"(1), 세 자리 "AAA" (1), 네 자리 "AAAA" ~ "AAAU"(5개), 다섯 자리 "AAAAA" ~ "AAAAU"(5x5개)이다. 

AAE전까지 세 자리(1) + 네 자리(5) + 다섯 자리(25)처럼 구할 수 있다. (알파벳 모음이 5개이므로, 확률)

따라서 1+2+(1+5+25) x1이란 식을 얻을 수 있다. 

AAI라면 AAA~, AAB~ 의 개수가 중복되므로 x2를 해줄 수 있다. 

다음과 같이 값을 구할 수 있다. 

 

 

고찰

걸린 시간: 한 시간

규칙을 찾기 위해서 노력했다. 처음 문제를 읽었을 때 감이 잡히지 않아서 하나씩 A부터 AAAE, AAE까지 값을 구해보았다. 하나씩 쓰면서 구하다 보니 규칙을 찾을 수 있었다.