[완전탐색] 모음사전 - JAVA

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

프로그래머스

---

이 문제는 단어의 최대 길이가 5이고 A, E, I, O, U 가 반복된다

따라서 이 문제의 예시를 통해 단어의 규칙을 찾아야 한다! (이게 어려웠다..🥺)

찾아본 결과, 사전의 순서는 다음과 같다는 것을 알아내었다!

 

순서가 좀.. 보이십니꺼..?

이걸 정리하면 다음과 같다!

 

 

문자열에 대한 자릿수 별 늘어나는 개수 파악하기

• 5번째 자리 : AEIOU 순서대로 바뀔 때마다 1씩 증가한다
• 4번째 자리 : AEIOU 순서대로 바뀔 때마다, 5번째 자리가 없는 경우를 포함하여 6 (1*5 + 1)씩 증가한다
• 3번째 자리 : AEIOU 순서대로 바뀔 때마다, 4번째 자리가 없는 경우를 포함하여 31 (6*5 + 1)씩 증가한다
• 2번째 자리 : AEIOU 순서대로 바뀔 때마다, 3번째 자리가 없는 경우를 포함하여 156 (31*5 + 1)씩 증가한다
• 1번째 자리 : AEIOU 순서대로 바뀔 때마다, 2번째 자리가 없는 경우를 포함하여 781 (156*5 + 1)씩 증가한다

💡 즉, 정리하자면 앞자리의 증가율 * 5 + 1 씩 증가하게 된다!

 

이제 위의 점화식을 통해서 문제를 해결하면 된다!

 

class Solution {
    public int solution(String word) {
        String str = "AEIOU";
        int[] x = {781, 156, 31, 6, 1};
        int answer = word.length();
        int index;
        System.out.println("init answer : "+answer+"\n");
        for(int i=0;i<word.length();i++) {
            index = str.indexOf(word.charAt(i));
            answer += x[i] * index;
        }
        return answer;
    }
}

 

---

참고)

https://bangu4.tistory.com/241

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