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

코딩테스트 연습(완전탐색) - 모음사전

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

프로그래머스

문제 설명

문자열이 주어지고 해당 문자열이 사전에서 몇번째에 있는지 찾는 문제이다.

사전에 사용되는 알파벳은 A,E,I,O,U 5가지이고 길이는 5까지이다. 사전에 등록되는 순서는 다음과 같다.

A-E-I-O-U 순으로 등록되고 A다음은 AA가 온다.

A -> AA -> AAA ... AAAAA -> AAAAE -> AAAAI ... UUUUU 순서이다.

문제 풀이

생각 과정

처음에는 진수변환을 해서 숫자를 계산해야하나 생각했었지만 알파벳이 5개, 길이도 최대 5개이므로 만들 수 있는 단어의 수가

1자리 단어 5개, 2자리 단어 5*5개 ... 5자리단어 5^5개 (5+25+125+625+3125)

따라서 총 3905개밖에 되지 않으므로 완전탐색으로 풀기로 했다.

알파벳을 하나씩 더해주며 확인해보고 주어진 문자열과 만든 단어가 동일하면 멈추도록 하였다.

구현

class Solution {
    static int ans,cnt;
    public static int solution(String word) {
        find(word, new StringBuilder());
        return ans;
    }

    public static void find(String word,StringBuilder sb){
        if(sb.toString().equals(word)){
            ans = cnt;
            return;
        }
        if(sb.length()==5) return;

        Character[] arr = new Character[]{'A','E','I','O','U'};

        for(int i=0;i<5;i++){
            cnt++;
            sb.append(arr[i]);
            find(word, sb);
            sb.deleteCharAt(sb.length()-1);
            if (ans!=0) return;
        }
    }
}

주의점

만들 수 있는 단어의 범위가 작아서 완전탐색으로 풀었으나 범위가 커지면 진수변환을 통한 방법이나

다른 성능개선 알고리즘을 떠올려야 할 것같다.

 

미루지말고 바로 구현해보자

static class Solution {
    public int solution(String word) {
        Map<Character, Integer> cMap = new HashMap<>();
        cMap.put('A', 0);
        cMap.put('E', 1);
        cMap.put('I', 2);
        cMap.put('O', 3);
        cMap.put('U', 4);
        int[] nums = new int[]{781, 156, 31, 6, 1};
        int answer = word.length();
        for (int i = 0; i < word.length(); i++) {
            char cur = word.charAt(i);
            answer += cMap.get(cur) * nums[i];
        }
        return answer;
    }
}

문자의 각 알파벳을 숫자로 변환하여 6진수로 생각하고 풀었다.

A = 10000

AA = 10000

AE = 12000

UUUUU = 55555

 

숫자가 1증가할 때마다 제일 끝 알파벳의 종류가 바뀐다.

즉 제일 끝 알파벳이 변하기 위해 필요한 수는 1이다. 

 

다음 자리 수를 생각해보면 6진수이기 때문에 1*5+1 = 6마다 알파벳의 종류가 바뀐다.

그 다음은 6*5+1 = 31마다 그 다음은 31*5+1 = 156 첫 자리는 156*5+1 = 781마다 종류가 바뀐다.

=> [자리수별 알파벳 전환을 위한 숫자] = [781, 156, 31, 6, 1]

 

단어의 길이만큼 1을 추가해주고(최소 A가 있기 때문)

E:1, I:2, O:3, U:4 를 위에서 계산한 [자리수별 알파벳 전환을 위한 숫자]만큼 곱해서 더해주는 방식으로 구현을 했다.

 

5자리밖에 되지 않음에도 시간이 상당히 빨라졌다.