[알고리즘] 프로그래머스 모음 사전 (레벨 2) / 자바 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
"AE"	158

---

입출력 예 설명

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

 

✏️ 문제 해결 방법

문제를 이해하는데 있어서는 두 번째 보는 것이 도움 되긴 했다. 처음 문제를 볼 때는 스스로 풀지는 못 했지만 규칙에 대해 바로 이해하지 못 했었는데 이번에는 규칙을 바로 이해해서 방법을 찾아 풀 수 있었는지도 모르겠다.

문자에서 n 번째 단어가 되는 규칙은 다음과 같다. 

따라서, 단어를 만들 수 있는 모음 {"A", "E", "I", "O", "U"} 다섯 가지를 모두 방문하며 탐색하는 완전 탐색 을 사용해야 한다. 

 

1. 모음을 넣어줄 배열, 완전탐색 하면서 만든 단어 넣어줄 ArrayList 생성

다섯개의 모음을 담은 배열과 생성한 단어를 넣어줄 list를 생성해준다. 단어는 생성될 때 마다 넣어줄 것이기 때문에 ArrayList 로 만들어 주었다.

 

2. 완전탐색

1) 리스트에 str 을 넣어준다.

2) 글자의 길이는 5 이하여야 한다.  만약, 5가 되었다면 돌아간다. 

➡️ 하나의 알파벳 탐색이 다 끝나면 다음 알파벳으로 넘어간다.

3) 완전탐색 반복

str 에 alp 배열의 알파벳을 하나 씩 붙이면서 탐색을 계속한다.

public void recursion(String str, int len) {

	A.add(str);

    if(len == 5) {
		return;
	}

    for(int i = 0 ; i < alp.length ; i++) {
		recursion(str + alp[i], len + 1);
	}
}

 

3. 주어진 단어 비교

주어진 단어 word와 리스트에 넣은 단어가 동일한지 비교하며 동일하면 리스트에 동일한 단어의 인덱스 번호를 get 해서 return 한다.

for(int i = 0 ; i < A.size(); i++) {
	if(A.get(i).equals(word)) return i;
}

위의 코드를 합치면 다음과 같다. 

 

 

>

전체 코드

import java.util.*;

public class Solution {
    
    static String[] alp;
    static ArrayList<String> A;
    
    public int solution(String word) {
        
        alp = new String[]{"A","E","I","O","U"};
        A = new ArrayList<>();
        
        String str = "";
        int len = 0;
        
        recursion(str, len);
        
        for(int i = 0 ; i < A.size(); i++) {
            if(A.get(i).equals(word)) return i;
        }
        return 0;
    }
    
    public void recursion(String str, int len) {
        
        A.add(str);
        
        if(len == 5) {
            return;
        }
        
        for(int i = 0 ; i < alp.length ; i++) {
            recursion(str + alp[i], len + 1);
        }
        
    }
}

 

🕸️ 문제 풀이 소감

완전탐색, 재귀 부분이 많이 약해서 문제를 많이 풀어봐야겠다 생각하는데 마주하면 자꾸 피하고싶어진다...ㅎㅎ 오늘도 문제를 풀고 다른 사람 풀이를 보며 입이 떠억 벌어졌다. 진짜 알고리즘 왕 고수들이 많은 듯 하다. 그리고 다른 사람들의 풀이를 보며 indexOf(String str) 라는 메서드를 처음 봤다. 

이렇게 알아가는 메서드들도 따로 정리를 해둬야겠다. 매번 처음 보는 것들이 생기고 공부할 게 정말 많은 듯 하다.  

 

---

궁금한 점이 있거나 잘못된 부분이 있다면 얼마든지 댓글로 남겨주세요 🤗

감사합니다!

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."