[프로그래머스] 모음 사전 - JAVA

- 링크 : https://programmers.co.kr/learn/courses/30/lessons/84512?language=java 

코딩테스트 연습 - 5주차_모음사전

 

- 참고 링크 : https://bangu4.tistory.com/241

[위클리챌린지] 5주 - 모음사전 - Java코드

 

- 풀이

 : 풀다가 모르겠어서 답을 참고하게 되었다.

 : A E I O U 가 하나씩 들어오는 순서가 아니라

 : A -> AA  -> AAA -> AAAA -> AAAAA 순으로 들어온다. (하나씩 규칙을 파악할 것이 아닌 전체의 흐름을 파악해야 한다.)
 : AAAA[A] : 가장 끝 자리가 하나씩 올라갈 때 마다 1(5의 0승) 씩 증가한다. 

 : AAA[A]A : 두번 째 끝 자리가 하나씩 올라갈 때 마다 6(5의 1승 + 5의 0승) 씩 증가한다.
  ( Ex. AAA[A]A -> AAA[A]E -> AAA[A]I ->  AAA[A]O ->  AAA[A]U ->  AAA[E] -> AAA[E]A)

 : AA[A]AA : 세번째 끝 자리가 하나씩 올라갈 때 마다 31(5의 2승 + 5의 1승 + 5의 0승) 씩 증가한다.

 ... 이러한 규칙들이 반복된다.

 

 : 그 이유는 A -> AA -> AAA -> AAAA -> AAAAA 가 약간 DFS 처럼 깊이 우선으로 도는데 이 때를 생각해보면 

 : 마지막 높이 노드에서 AAAAA -> AAAAE 라고 하면 1개만 탐색하면 바로 다음 것을 찾을 수 있고

 : 두번 째 마지막 높이 노드 AAAAA -> AAAEA 는 마지막 노드 A, E, I, O, U 를 다 탐색(4번 이동)하고 다음 탐색하는 것이  다른 두번 째 높이 노드의 AAAE 5번 째 이동이고 AAAEA 는 6번 째가 된다. 이러한 원리로 하나씩 올라 갈 때마다 5(현재 각 층마다 노드 개수가 5개 이므로) 5의 n승 만큼 증가하게 되는 것이다.

 

 - 피드백

 : 규칙을 좀 더 넓게 보는 습관, 수학적으로 좀 더 생각하는 습관을 들여야겠다.

 

 - 코드

 

class Solution {
    
    public int solution(String word) {
		String str = "AEIOU";
		int[] dp = new int[5];
        dp[0] = 1;
        for (int i=1; i<5; i++) {
            dp[i] = (int) Math.pow(5, i) + dp[i-1];
        }
        
		int index,result = word.length();
        
		for(int i=0; i<word.length(); i++){
			index = str.indexOf(word.charAt(i));
			result += dp[4-i] * index;
		}
        
		return result;
    }
}