[99클럽 코테 스터디 9일차 TIL] 프로그래머스 - 모음사전

체감 난이도 = 중

https://school.programmers.co.kr/learn/courses/30/lessons/84512?language=java

문제 분석 및 설계

처음에는 수학적으로 접근하려했는데, 순서를 계산하는 로직을 어떻게 짜야할지 감이 잘 오지 않았습니다.

한 자리 경우의 수 = 5^1 = 5
두 자리 경우의 수 = 5^2 = 25
세 자리 경우의 수 = 5^3 = 125
네 자리 경우의 수 = 5^4 = 625
다섯 자리 경우의 수 = 5^5 = 3125
모든 경우의 수 = 3905

모든 경우의 수가 3905로 매우 적기때문에, 완탐으로 구현해도 되겠다고 생각했습니다.
백트래킹 방식으로 모든 경우의 수를 탐색했습니다.

코드

import java.util.*;

class Solution {
    private static int len = 5;
    private String[] alpha = {"A", "E", "I", "O", "U"};
    private int num = -1;
    private String word = "";
    private boolean found = false;
    
    public int solution(String word) {
        this.word = word;
        
        backtracking(new StringBuilder());
        
        return num;
    }
    
    public void backtracking(StringBuilder str) {
        num++;
        if (word.contentEquals(str)) {
            found = true;
            return;
        }
        
        if (str.length() == 5) return;
            
        for (int i = 0; i < alpha.length; i++) {
            str.append(alpha[i]);
            if (!found) backtracking(str);
            str.deleteCharAt(str.length()-1);
        }
    }
}

코드 개선1

같은 dfs풀이인데, 코드가 간결해서 가져왔습니다.

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

제 코드와 다른점은 아래와 같습니다.

• 어차피 총 경우의 수가 적기 때문에 word와 같은 순간에 dfs를 그만하도록 구현하기보다, 가능한 모든 경우의 수를 list에 넣어둡니다. 그리고 list.indexOf(word);를 return 합니다.

코드 개선2

수학적으로 풀 수 있습니다

class Solution {
    public int solution(String word) {
        int answer = 0, per = 3905;
        for(String s : word.split("")) answer += "AEIOU".indexOf(s) * (per /= 5) + 1;
        return answer;
    }
}