[240417] 알고리즘 리부트 50일차 - 프로그래머스 모음사전 자바

기본적으로 재귀의 방식으로 구현하면 된다. 다섯가지의 문자로 길이 5의 문자열을 만드는 경우의 수가 5000가지 이하이므로 시간을 고려하지는 않았다. 그래도 글자에 + 하는 건 비효율이라고 생각해서 스트링빌더를 사용했다. 그리고 오래 가지 않도록 답을 찾으면 return 하도록 구현했다.

import java.util.*;
class Solution {
    public static char [] arr = {'A', 'E', 'I', 'O', 'U'};
    public static String target;
    public static int tmp, answer;
    public int solution(String word) {
        tmp = 0;
        answer = -1;
        target = word;
              
        StringBuilder sb = new StringBuilder();
        
        int length = sb.length();

        makeWords(sb, length);        
        
        return answer;
    }
    
    public static void makeWords(StringBuilder sb, int currLength){
        
        if (sb.toString().equals(target)){
            answer = tmp;
            return;
        }

        if (currLength == 5) return;


        for (int i = 0; i < arr.length; i++) {
            if (answer != -1) {
                return;
            }
            //System.out.println("currLength: " + currLength);
            if(sb.length()>currLength) sb.deleteCharAt(currLength);
            sb.insert(currLength, arr[i]);
            //System.out.println("현재 문자열: " + sb);
            tmp++;
            //System.out.println("현재 수: " + tmp);
            makeWords(sb, currLength + 1);
        }
        sb.deleteCharAt(currLength);
    }
}

아래는 친구 코드 뭐 이렇게 간단해... 그래 근데 간단하게 푸는 게 맞아.. 속상

import java.util.*;

class Solution {
    static char[] arr = {'A', 'E', 'I', 'O', 'U'};
    static Map<String, Integer> dir = new HashMap<>();
    static int order = 0;
    public int solution(String word) {
        rec("", word, 0);
        return dir.get(word);
    }
    
    private void rec(String now, String word, int d) {
        dir.put(now, order++);
        if(d==5) {
            return;
        }
        for(int i=0; i<5; i++) {
            //System.out.println(now+arr[i]);
            rec(now + arr[i], word, d+1);
        }
    }
}