프로그래머스_모음사전(JAVA)

[문제 풀이]

수학과 완전탐색을 이용하여 문제를 풀었습니다.

 

모음사전 문제는 주어진 문자열이 AEIOU로 이루어진 사전의 몇번째로 등장하는지를 찾는 문제입니다. 문제를 풀 수 있는 방법은 여러가지가 있지만 수학, 완전탐색 두 가지 방법으로 풀어보았습니다.

 

수학으로 푸는 방법은 아래와 같습니다.

자리별 모음의 순번을 담은 배열을 생성합니다. 

AAAAA ~ AAAAE 1
AAAA   ~ AAAE    (1*5) + 1 = 6
AAA     ~ AAE       (1*5+1) * 5 + 1 = 31
AA       ~ AE          ((1*5+1) * 5 + 1) * 5  + 1 = 156
A          ~ E            (((1*5+1)*5+1)*5+1)*5+1  = 781

해당 배열을 이용하여 자리 수 * index 수를 곱해서 더합니다.

 

완전탐색으로 푸는 방법은 아래와 같습니다.

 DFS를 통해 만들 수 있는 모든 문자열을 list에 더 해준 후, list의 index를 구해줍니다.

[JAVA]

import java.util.*;

//수학
class Solution {
    public int solution(String word) {
        String str = "AEIOU";
		int[] x = {781, 156, 31, 6, 1};
        
		int index;
        int result = word.length();
        
		for(int i = 0; i < word.length(); i++){
			index = str.indexOf(word.charAt(i));
			result+= x[i] * index;
		}
		return result;
    }  
}

[JAVA]

import java.util.*;

class Solution {
    ArrayList<String> dictionary = new ArrayList<>();
    
    public int solution(String word) {
        DFS("", 0);
        return dictionary.indexOf(word);
    }
    
    void DFS(String str, int len){   
        if(len > 5)
            return;
        dictionary.add(str);
        
        for(int i = 0; i < 5; i++)
            dfs(str + "AEIOU".charAt(i), len + 1);
    }
}