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

문제내용

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

코딩테스트 연습 - 모음사전

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• word의 길이는 1 이상 5 이하입니다.
• word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

---

문제풀이

먼저 문제가 쉬워보였으나 생각보다 어려웠고, 풀지 못했다. 그래서 어떤 천재같은 사람의 풀이를 보면서 이해하려고 했는데 그 풀이를 설명해야겠다..

 

대부분의 사람들은 DP를 풀때처럼 규칙을 먼저 찾았는데, 그 규칙은 다음과 같다.

1 A
2 AA
3 AAA
4 AAAA

//1씩 증가
5 AAAAA
6 AAAAE
7 AAAAI
8 AAAAO
9 AAAAU

//6씩 증가
10 AAAE
11 AAAEA
12 AAAEE
13 AAAEI
14 AAAEO
15 AAAEU
16 AAAI

...

사전순서대로 16번까지 나열해보면 위와 같은 순서로 나오는데 이때 규칙을 찾기 위해 먼저 경우의수를 파악한다.

-> 5번째 자리에서 문자간의 간격은 1

-> 4번째 자리에서 문자간의 간격은 6 ( ex. AAAE ~ AAAI )

 

※ 주어진 문자열 길이와 문자 수에 따른 경우의수 구하기

문자수는 5, 문자열 길이가 1일때 = 5 ^ 1 = 5

문자수는 5, 문자열 길이가 2일때 = 5 ^ 2 = 25

문자수는 5, 문자열 길이가 3일때 = 5 ^ 3 = 125

문자수는 5, 문자열 길이가 4일때 = 5 ^ 4 = 625

문자수는 5, 문자열 길이가 5일때 = 5 ^ 5 = 3125

총 경우의수 = 5 + 25 + 125 + 625 + 3125 = 3905

 

그리고 위에서 나열해놓은 단어들을 보면 각 문자간의 간격은 1씩 증가하는걸 볼수 있다. ( ex. AAAAE -> AAAAI ... )

그다음을 살펴보면 문자열 길이가 4일때는 간격이 6씩 증가한다는걸 알수 있다. ( ex. AAAE -> AAAI ... )

 

위를 토대로

n번째에서 문자간의 간격 = 총 경우의 수/(5 or 25 or 125 or 625 or 3125)  가된다. 즉,

다섯 번째에서 문자간의 간격 = 3905/3125 = 1

네 번째에서 문자간의  간격 = 3905/625 = 6

세 번재에서 문자간의 간격 = 3905/125 = 31

두 번째에서 문자간의 간격 = 3905/25 = 156

첫 번째에서 문자간의 간격 = 3905/5 = 781

이 된다는걸 알수 있다.

 

이렇게 구한값으로 사전에 몇번째로 등록된 문자열인지 구해주면 된다.

예를들어 문제에서 처럼 {A, E, I, O, U} 순서로 문자가 나열된다는 기준으로 한다면

 

AAAU 의경우 

AAAU = (781*0)+1 + (156*0)+1 +(31*0)+1 + (6*4)+1 = 29 이 나오는데 

각 자리수에서 +1을 해주는 이유는 문자 A가 왔을때의 경우 하나를 더해주는 과정이다.

 

IOA 의경우

IOA = (781*2)+1  + (156*3)+1 + (31*0)+1 = 2033 이 나오고 위와 같은 이유로 각자리에서 +1을 해준다.

 

핵심은 규칙을 찾아보고 총 경우의 수/(5 or 25 or 125 or 625 or 3125) 이부분을 생각해 내는게 중요하다고 생각한다.

 

---

코드

public class Solution {
    public int solution(String word) {
        int answer = 0;
        int total = 0, charCnt=5;//총경우의 수, 문자개수
        
        for(int i=1; i<=charCnt; i++)  
        	total += Math.pow(charCnt, i);
        
        //i번째 문자에서 문자하나 마다의 간격을 저장해줄 배열
        int[] charDis = new int[charCnt];
        for(int i=0; i<charCnt; i++) 
        	charDis[i] = (int) (total/Math.pow(charCnt, i+1));
        
        
        //사전에 몇번째로 등록됐는지 계산
        for(int i=0; i<word.length(); i++) {
        	char ch = word.charAt(i);
        	if(ch=='A') answer += (charDis[i]*0) + 1;
        	else if(ch=='E') answer += (charDis[i]*1) + 1;
        	else if(ch=='I') answer += (charDis[i]*2) + 1;
        	else if(ch=='O') answer += (charDis[i]*3) + 1;
        	else answer += (charDis[i]*4) + 1;
        }
        
        System.out.println(answer);
        return answer;
    }
}

---

마치며

이런 류의 문제에 익숙하지 않아서 그런지는 몰라도 레벨2 문제지만 개인적으론 레벨 3같은 2였다고 생각한다... 

그리고 위의 공식을 찾아낸 사람은 어떻게 저런 생각을 했을까... 나열했을때 규칙이 어느정도 보여도 그걸 경우의수를 이용해 점화식으로 표현한다는게 대단하다고 본다 ㄷㄷㄷ