[Java] 프로그래머스 : 모음사전

문제

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

프로그래머스

 

풀이 과정

처음엔 AEIOU 순서대로 DFS방식을 통해 사전순대로 읽어가면서 해당 문자열을 만나면 return하는 방식이 떠올랐다. 그런데, 굳이 순서대로 다 탐색하는 것보다 몇 번째인지 바로 계산할 수 있는 방식이 있어서 이 방식으로 구현했다. 원래는 O(N)만큼 걸리는 알고리즘을 O(1)으로 구현할 수 있는 것이다.

 

수식 : 5^(length("AEIOU")-1-i) + sum(1*5^(0~(length("AEIOU")-2-i)))

class Solution {
    
    public int solution(String word) {
        int answer = 0, len = word.length();
        for(int i=0; i<len; i++){
            answer += count("AEIOU".indexOf(word.charAt(i)), i) + 1;
        }
        return answer;
    }
    
    public int count(int order, int i){
        int sum = 0, temp = 1;
        for(int a=0; a<=3-i; a++){
            sum += temp;
            temp*=5;
        }
        return order * ((int)Math.pow(5, 4-i) + sum);
    }
    
}