🎯문제
사전에 알파벳 모음 '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.*;
class Solution {
// 모음을 따로 저장
char[] alphabet = {'A', 'E', 'I', 'O', 'U'};
// 사전에 들어갈 모든 경우의 수를 저장할 배열
ArrayList<String> list;
// 깊이 우선 탐색
public void dfs(String result) {
// 값을 저장
list.add(result);
// 문자열의 길이가 5라면 반환해줌
if(result.length() == 5) {
return;
}
// 모음을 저장한 배열을 돌면서 값을 넣어줌
for(int i = 0; i < alphabet.length; i++) {
dfs(result + alphabet[i]);
}
}
public int solution(String word) {
int answer = 0;
list = new ArrayList<>();
dfs("");
// list에 저장된 값을 하나씩 탐색
for(int i = 1; i < list.size(); i++) {
// 찾으려는 단어와 같다면
if(list.get(i).equals(word)) {
// 해당 위치의 인덱스를 저장
answer = i;
break;
}
}
return answer;
}
}설명
사전에 들어갈 모음 배열과 모든 경우의 수를 저장할 배열을 만든 뒤 깊이 우선 탐색을 통해 모든 경우의 수를 저장해준다.
깊이 우선 탐색을 진행할 때 탐색된 순서는 사전에 들어가는 순서이며, 이 모든 경우의 수를 배열에 저장해준다. 또한 문자열의 길이가 1~5 사이이므로, 문자열의 길이가 5라면 더이상의 탐색은 중지하고 반환을 시켜준다.
모든 탐색이 끝난 뒤에 배열에 저장된 크기만큼 반복을 진행하여 찾고자 하는 값과 하나씩 비교를 진행한다. 이때 값이 같다면 해당 위치의 인덱스가 사전에 들어간 순서가 된다.
여기서 인덱스는 0부터 시작하니까 -1을 해줘야하는 것이 아닌가? 라는 생각이 들 수 있는데, 깊이 우선 탐색을 처음 진행할 때 ""를 맨 처음 넘겨주었고, 이 값 역시 배열의 인덱스 값 0에 저장되어있다. 이후 "A"가 인덱스 1에 저장이 되며, 그 후 순서대로 값이 저장이 되기 때문에 -1을 해줄 필요없이 현재 인덱스 값을 반환해주면 된다.
💡느낀 점
최근 여러 문제들을 풀면서 여러 함수들을 사용했던터라 아무 함수의 사용없이 깊이 우선 탐색 함수를 만들어서 문제를 푸니 생각보다 간단하게 풀었던 것 같다. Lv2를 간단하게 풀었다고 생각하다니 그래도 꾸준하게 문제를 푸니 실력이 늘긴 하는 것 같아 뿌듯했다.
링크
