프로그래머스 [ 모음사전 / Lv2 ] - JAVA

문제 링크

 

---

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

프로그래머스

 

 

문제 설명

---

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

 

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

---

• word의 길이는 1 이상 5 이하입니다.
• word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

 

입출력 예

---

입출력 예 설명

입출력 예 #1
사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. "AAAAE"는 사전에서 6번째 단어입니다.

입출력 예 #2
"AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다.

입출력 예 #3
"I"는 1563번째 단어입니다.

입출력 예 #4
"EIO"는 1189번째 단어입니다.

 

코드

---

public class 모음사전 {
    private static String vowel = "AEIOU";
    private static int cnt = 0;
    private static int answer = 0;

    public int solution(String word) {
        StringBuilder sb = new StringBuilder();
        dfs(word, sb);
        return answer;
    }
    private static void dfs(String word, StringBuilder sb) {
        if (sb.toString().equals(word)) {
            answer = cnt;
            return;
        }
        if (sb.length() == vowel.length()) {
            return;
        }
        for (char c : vowel.toCharArray()) {
            sb.append(c);
            cnt++;
            dfs(word, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

 

알고리즘 설명

---

[ 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다. ] 라는 규칙에 따라,

빈 문자열부터 시작해서 "AEIOU" 로 만들 수 있는 모든 조합을 DFS로 탐색합니다. 탐색의 횟수는 cnt를 통해 저장하고, 탐색 도중 word와 sb를 비교하여 같다면 해당 탐색 횟수를 answer에 저장합니다.

 

코드 해석

---

String vowel을 "AEIOU"로 설정하고, vowel을 toCharArray를 사용하여 char로 배열화하여, DFS 탐색을 진행합니다.

DFS 호출로 인해 sb에 문자가 추가되었다면, 호출 이후에는 deleteCharAt()을 사용해 마지막 문자를 삭제함으로써 sb를 이전 상태로 되돌려 백트래킹이 가능하도록 합니다.

 

+ 리팩토링 코드🏭

---

public class 모음사전 {
    private static String vowel = "AEIOU";
    private static int cnt = 0;
    private static int answer = 0;

    public int solution(String word) {
        StringBuilder sb = new StringBuilder();
        dfs(word, sb);
        return answer;
    }
    private static void dfs(String word, StringBuilder sb) {
        if (word.contentEquals(sb)) {
            answer = cnt;
            return;
        }
        if (sb.length() == vowel.length()) {
            return;
        }
        for (char c : vowel.toCharArray()) {
            sb.append(c);
            cnt++;
            dfs(word, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

 

sb.toString().equals(word)는 StringBuilder를 toString()으로 변환하며 새로운 문자열 객체를 생성한 뒤, word와 비교하기 때문에

if 조건문이 실행될 때마다 객체가 생성되어 메모리 낭비가 발생합니다.

반면, word.contentEquals(sb)는 StringBuilder를 불필요한 객체 생성 없이 직접 String과 비교하므로, 메모리 사용 측면에서 효율적입니다.