[Programmers] 모음사전 - Java

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

프로그래머스

---

1. 문제

A, E, I, O, U로 만들 수 있는 길이가 5 이하인 단어가 수록된 사전이 있다.

특정 단어가 주어졌을 때, 사전에서 몇 번째 단어인지 반환한다.

 

2. 풀이

재귀를 사용하였다.

map을 사용하여 단어, index를 저장하면서 사전역할을 하였다.

1. 초기값은 "", depth 0으로 출발한다.

2. 재귀를 돌 때마다 map에 단어와 순서를 넣어준다.

3. 그리고 depth가 5가 되면(단어 길이가 5) return해주어 다시 이전 상태로 돌아간다.

4. 이전 상태에서 다음 알파벳을 붙여주며 반복한다.

재귀가 끝난 후, map에서 주어진 단어를 get했을 때의 value값이 순서이므로 이것을 반환하면 끝이다.

 

3. 코드

import java.io.*;
import java.util.*;

class Solution {
    
    static String[] arr = { "A", "E", "I", "O", "U"};
    static int index = 0;
    static Map<String, Integer> map = new HashMap<> ();
    
    public int solution(String word) {
        int answer = 0;
        
        recursion("", 0);
        answer = map.get(word);
        
        return answer;
    }
    
    static void recursion(String s, int depth) {
        map.put(s, index++);
        
        if (depth == 5) return;
        
        for (int i=0; i<5; i++) {
            recursion(s+arr[i], depth+1);
        }
    }
}

 

4. 사담

처음에 부분집합, 순열로 접근했어서 시간이 많이 걸렸다.

역시 최대한 많이 풀어봐야 장땡인듯하다.