[99클럽 코테 스터디 16일차 TIL] 프로그래머스 - 모음사전
99클럽 코테 스터디 16일차 TIL 입니다.
[level 2] 모음 사전 - 84512
구분
완전탐색
문제 설명
사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.
단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.
제한사항
word의 길이는 1 이상 5 이하입니다.
word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.
입출력 예
"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번째 단어입니다.
풀이 코드
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 하도록 구현해서 메모리 사용량에서 조금 더 개선해봤다.
돌아보기
여전히 재귀 함수는 익숙하지 않고 완전히 이해하지 못해서 구현하는데 시간이 오래 걸린다. 재귀 함수를 문제들을 자주 풀어보면서 뇌를 말랑말랑하게 해야겠다.
다음에는
조금 더 깊게 생각해보기
BFS, DFS 공부하기
#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL
Last updated