[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'로만 이루어져 있습니다.

---

입출력 예

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

---

풀이 코드

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