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 문을 다섯번 중첩해서 정말 단순하게 풀었다. 그리고 재귀로 개선해봤다.
개선하기
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() 메서드를 한번만 호출해서 해결하기 위해 한번 더 개선해봤다.
개선하기 + 개선하기
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 와 생성한 문자열이 동일하면 재귀를 끊어내고 싶어서 아래와 같이 한번 더 개선해봤다.
개개개선하기
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 하도록 구현해서 메모리 사용량에서 조금 더 개선해봤다.
돌아보기
여전히 재귀 함수는 익숙하지 않고 완전히 이해하지 못해서 구현하는데 시간이 오래 걸린다. 재귀 함수를 문제들을 자주 풀어보면서 뇌를 말랑말랑하게 해야겠다.
