[프로그래머스] 모음 사전_자바

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

프로그래머스

---

이 문제가 완전탐색 카테고리에 들어가 있어서 처음에는 DFS로 풀었다. 

답은 맞았지만 효율적이지 못하다는 생각이 들어 더 찾아봤다.

 

규칙을 찾아 조금 더 수학적으로 접근하는 방법이 있었다.

 

 

규칙을 통해 2번째, 1번째 문자는 몇 번만에 바뀌는지 알 수 있다.

5번째 문자 바뀔 때 = 1

4번째 문자 바뀔 때 = 1 + 5^1 = 6

3번째 문자 바뀔 때 = 6 + 5^2 = 31

2번째 문자 바뀔 때 = 31 + 5^3 = 156

1번째 문자 바뀔 때 = 156 + 5^4 = 781

  

문제 푸는 법을 자세히 설명하면,

word = "AAAAE"

첫 번째 A는 A,E,I,O,U 중 가장 앞에 있는 문자이기 때문에 (781 * 0+1)

두 번째 A도 위와 같은 이유로 (156 * 0+1)

세 번째 A도 위와 같은 이유로 (31 * 0+1)

네 번째 A도 위와 같은 이유로 (6 * 0+1)

다섯 번째 E는 A,E,I,O,U 중 두 번째 문자이기 때문에 (1*1+1)

=> 각 위치 값을 더하면 6번째 단어라는 것을 알 수 있다.

 

word = "EIO"

첫 번째 E는 A,E,I,O,U 중 두 번째 문자이기 때문에 (781 * 1+1)

두 번째 I는 A,E,I,O,U 중 세 번째 문자이기 때문에  (156 * 2+1)

세 번째 A도 위와 같은 이유로 (31 * 3+1)

=> 각 위치 값을 더하면 6번째 단어라는 것을 알 수 있다.

 

각 자리에서 +1을 하는 이유는 +1을 하기 전까지는 전 문자까지의 순서이기 때문이다.

 

---

[ DFS를 이용한 코드 ]

public class P7 {
    static int answer = 0, cnt=0;
    static char[] a = {'A','E','I','O','U'};
    static String words;
    public static void main(String[] args){
        P7 p = new P7();
        String word = "AAAAE";
        System.out.println(p.solution(word));
    }
    public int solution(String word) {
        words = word;
        dfs("",0);
        return answer;
    }
    public static void dfs(String str, int idx){
        if(str.equals(words)){
            answer = cnt;
            return;
        }
        cnt++;
        if(idx > 4) return;

        for(int i=0; i<a.length; i++){
            dfs(str+a[i],idx+1);
        }
    }
}

 

[ 규칙을 찾아서 푼 코드 ]

public class P7 {
    static String str = "AEIOU";
    static int[] x = {781,156,31,6,1};
    public static void main(String[] args){
        P7 p = new P7();
        String word = "AAAAE";
        System.out.println(p.solution(word));
    }
    public int solution(String word) {
        int answer = 0;
        for(int i=0; i<word.length(); i++){
            int tmp = str.indexOf(word.charAt(i));
            answer += (x[i]*tmp)+1;
        }
        return answer;
    }
}