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

## \[level 2] 모음 사전 - 84512

[문제 링크](https://school.programmers.co.kr/learn/courses/30/lessons/84512?language=java)

#### 구분

완전탐색

#### 문제 설명

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

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

**제한사항**

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

***

**입출력 예**

| word      | result |
| --------- | ------ |
| `"AAAAE"` | 6      |
| `"AAAE"`  | 10     |
| `"I"`     | 1563   |
| `"EIO"`   | 1189   |

**입출력 예 설명**

입출력 예 #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번째 단어입니다.

***

## 풀이 코드

```java
import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(String word) {
        Map<String, Integer> map = new HashMap<>();
        String[] arr = {"A", "E", "I", "O", "U"};
        int index = 1;
        for (int i = 0; i < 5; i++) {
            map.put(arr[i], index++);
            for (int j = 0; j < 5; j++) {
                map.put(arr[i] + arr[j], index++);
                for (int k = 0; k < 5; k++) {
                    map.put(arr[i] + arr[j] + arr[k], index++);
                    for (int o = 0; o < 5; o++) {
                        map.put(arr[i] + arr[j] + arr[k] + arr[o], index++);
                        for (int p = 0; p < 5; p++) {
                            map.put(arr[i] + arr[j] + arr[k] + arr[o] + arr[p], index++);
                        }
                    }
                }
            }
        }
        
        return map.get(word);
    }
}
```

* Time: 57.07 ms
* Space: 80.2 MB

배열 크기가 5 밖에 안되기 때문에 `for` 문을 다섯번 중첩해서 정말 단순하게 풀었다. 그리고 재귀로 개선해봤다.

### 개선하기

```java
import java.util.Map;
import java.util.HashMap;

class Solution {
    
    private Map<String, Integer> map = new HashMap<>();
    private int index = 0;
    
    
    public int solution(String word) {
        String[] vowels = {"A", "E", "I", "O", "U"};
        
        for (int i = 0; i < 5; i++) {
            insert(vowels, "", i);
        }
        
        return map.get(word);
    }
    // vowel, depth : "", 0 -> "A", 0 -> ...
    public void insert(String[] vowels, String vowel, int depth) {
        if (vowel.length() == 5) return;
        String word = vowel + vowels[depth]; // "" + "A" -> "A" + "A" -> ...
        index++; // 1 -> 2
        map.put(word, index); // "A", 1 -> "AA", 2 -> ...
        for (int i = 0; i < 5; i++) {
            insert(vowels, word, i); // word, i : "A", 0 -> ...
        }
    }
}
```

* Time: 14.45 ms
* Space: 81 MB

재귀이긴한데 뭔가 부족한 재귀 풀이다. `insert()` 메서드만 보면 첫번째 문자열을 스스로 전달하고 있지 않아서 만약 문자열 `"A"` 만 전달하게 되면 `"AAAAU"` 에서 재귀는 끝나버린다.\
이를 해결하기 위해 반복문을 통해 `insert()` 메서드를 호출하고 있는 상태다. `insert()` 메서드를 한번만 호출해서 해결하기 위해 한번 더 개선해봤다.

### 개선하기 + 개선하기

```java
import java.util.Map;
import java.util.HashMap;

class Solution {
    
    private Map<String, Integer> map = new HashMap<>();
    private int index = 0;
    
    
    public int solution(String word) {
        String[] vowels = {"A", "E", "I", "O", "U"};

        insert(vowels, "");

        return map.get(word);
    }
    
    public void insert(String[] vowels, String vowel) {
        map.put(vowel, index++);
        if (vowel.length() == 5) return;
        for (int i = 0; i < 5; i++) {
            insert(vowels, vowel + vowels[i]);
        }
    }
}
```

* Time: 5.6 ms
* Space: 79 MB

이러면 `insert()` 메서드 스스로가 첫번째 문자열을 전달해줄 수 있다. 하지만 여전히 아쉬운 부분은 `word` 문자열과 동일한 문자열이 생성되더라도 재귀는 끝까지 진행되기 때문에 시간이 오래 걸린다고 생각했다.

그래서 `word` 와 생성한 문자열이 동일하면 재귀를 끊어내고 싶어서 아래와 같이 한번 더 개선해봤다.

### 개개개선하기

```java
import java.util.Map;
import java.util.HashMap;

class Solution {
    
    private Map<String, Integer> map = new HashMap<>();
    private int index = 0;
    private boolean isWord = false;
    
    
    public int solution(String word) {
        String[] vowels = {"A", "E", "I", "O", "U"};

        insert(vowels, "", word);

        return map.get(word);
    }
    
    public void insert(String[] vowels, String vowel, String word) {
        map.put(vowel, index++);
        if (vowel.equals(word)) {
            isWord = true;
            return;
        }
        if (vowel.length() == 5 || isWord) return;
        for (int i = 0; i < 5; i++) {
            insert(vowels, vowel + vowels[i], word);
        }
    }
}
```

* Time: 5.82 ms
* Space: 74.7 MB

`word` 문자열과 동일한 문자열을 생성하면 `isWord` 라는 `boolean` 값을 `true` 로 변경하고 `true` 인 경우에 `return` 하도록 구현해서 메모리 사용량에서 조금 더 개선해봤다.

***

## 돌아보기

여전히 재귀 함수는 익숙하지 않고 완전히 이해하지 못해서 구현하는데 시간이 오래 걸린다. 재귀 함수를 문제들을 자주 풀어보면서 뇌를 말랑말랑하게 해야겠다.

### 다음에는

* 조금 더 깊게 생각해보기
* BFS, DFS 공부하기

***

\#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://devlee.gitbook.io/docs/study/99/99-16-til.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.