출처: https://school.programmers.co.kr/learn/courses/30/lessons/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번째 단어입니다.
일단, 자바에는 파이썬처럼 간편한 itertools.product() 같은 게 없어서, 직접 재귀(백트래킹) 로 문자열 조합을 생성해줘야 한다.
그리고 나는, 백트래킹, dfs에 대한 개념이 너무 없었다.
'A', 'E', 'I', 'O', 'U' 이 다섯 글자를 이용해서, 길이 1부터 5까지의 모든 가능한 조합을 만든다.
void dfs(String word, int depth) {
if (depth > 5) return;
// 만들어진 단어 저장
list.add(word);
for (char c : 모음들) {
dfs(word + c, depth + 1);
}
}이런 구조로 재귀 함수를 만들고, 이 리스트를 만든 다음 사전순 정렬을 하고, 주어진 단어가 몇 번째인지 indexOf()로 찾아서 +1 해주면 된다.
-
재귀로 모든 조합 만들기 (depth 제한 5)
-
리스트에 저장
-
정렬
-
word 위치 찾기
전역 리스트 – 조합된 문자열들을 담아 둘 List list.
모음 배열 – 예를 들면 char[] vowels = {'A', 'E', 'I', 'O', 'U'};
dfs("", 0); 으로 시작하면 ""부터 시작해서 'A', 'AA', ... 'UUUUU' 까지 모두 탐색
전체적인 간단한 흐름을 정리하자면
List<String> list = new ArrayList<>();
char[] vowels = {'A', 'E', 'I', 'O', 'U'};
void dfs(String word, int depth) {
if (depth > 5) return;
if (!word.isEmpty()) list.add(word); // 빈 문자열은 제외할 수도 있다
for (char c : vowels) {
dfs(word + c, depth + 1);
}
}각 단계에서 모음 5개 중 하나를 추가해서 재귀 호출.
최대 깊이 5에서 멈춤 → 최대 5글자까지의 조합만 생성됨.
총 조합 수는 5^1 + 5^2 + 5^3 + 5^4 + 5^5 = 3905개
✅ 해야 할 일 정리:
모음 리스트 초기화
char[] vowels = {'A', 'E', 'I', 'O', 'U'};
단어 저장 리스트 초기화
List list = new ArrayList<>();
DFS 실행
dfs("", 0);
사전순 정렬
Collections.sort(list);
해당 단어의 인덱스 반환
return list.indexOf(word) + 1;
(+1을 해야 문제에서 요구하는 순서랑 맞음)
전체 코드 정리
public int solution(String word) {
List<String> list = new ArrayList<>();
char[] vowels = {'A', 'E', 'I', 'O', 'U'};
dfs("", 0, list, vowels);
Collections.sort(list); // 사전순 정렬
return list.indexOf(word) + 1;
}
private void dfs(String current, int depth, List<String>list, char[] vowels) {
if (depth > 5) return;
if (!current.isEmpty()) list.add(current);
for (char c : vowels) {
dfs(current + c, depth + 1, list, vowels);
}
}
일단, 전반적인 dfs, 백트래킹에 대한 기본적인 문제였다.
특히 나는 dfs 메서드 자체는 이해가 갔다.
5글자 넘기면 안되고, current 변수가 비어있지 않을 때 리스트에
추가시키되
for (char c : vowels) {
dfs(current + c, depth + 1, list, vowels);
} 이부분은 이해가 잘 안 갔다.
반복문안에서 벌어지고 있는일..
dfs("A", 1) → 그 안에서
dfs("AA", 2)
dfs("AE", 2)
dfs("AI", 2)
...
이런 식으로 한 가지 조합을 계속 이어붙여가며 재귀 호출하는 것이다.
이런식으로 트리 구조를 만들어가는 것.
"" (root)
├── A
│ ├── AA
│ │ ├── AAA
│ │ └── ...
│ └── AE
├── E
│ ├── EA
│ └── ...
└── ...
지금 current = "A", depth = 1이면
그다음 가능한 경우는 모두:
"AA", "AE", "AI", "AO", "AU"
그리고 "AA"에 대해서 또 똑같이 5개 붙일 수 있으니:
"AAA", "AAE", "AAI", "AAO", "AAU"
이렇게 5^depth 만큼의 경우의 수가 트리처럼 뻗어 나가고 있는 것
즉,
반복문은 선택지를 의미하고
재귀는 그 선택을 기반으로 다음 선택지를 더 이어가는 것이다.
✅ 요약
| 구조 | 의미 |
|---|---|
for (char c : vowels) | 이번 위치에 어떤 글자를 넣을까? (선택지 5개) |
dfs(current + c, ...) | 선택했으니, 다음 글자를 이어서 또 탐색하자 (다음 단계로 재귀) |
다른 분들 풀이
import java.util.*;
class Solution {
List<String> list = new ArrayList<>();
void dfs(String str, int len) {
if(len > 5) return;
list.add(str);// 지금까지 만든 단어(str)를 리스트에 저장.
for(int i = 0; i < 5; i++)
dfs(str + "AEIOU".charAt(i), len + 1);// 모음 다섯 개(A, E, I, O, U)에 대해 반복.
// 현재 단어에 모음 하나 붙여서 다음 깊이로 넘어감. str + 모음을 통해 새로운 단어 조합을 만들어 나감.
}
public int solution(String word) {
dfs("", 0);
return list.indexOf(word);
}
}import java.lang.Math;
class Solution {
public int solution(String word) {
int answer = word.length();
int pos;
for(pos = 0; pos < word.length(); pos ++){
char c = word.charAt(pos);
if(c=='A') continue;
int temp = 0;
for(int i = 0; i <= 4-pos; i++){
temp += Math.pow(5,i);
}
answer += temp*val(c);
}
return answer;
}
public int val(char c){
if(c=='E') return 1;
else if(c=='I') return 2;
else if(c=='O') return 3;
else return 4;
}
} class Solution {
public int solution(String word) {
int answer = 0;
int mul = 781;// 781은 5자리에서 가능한 모든 조합 수의 총합:
char chr[] = {'A', 'E', 'I', 'O', 'U'};// 사전 순서 모음 배열
for(int i=0; i<word.length(); i++){
for(int j=0; j<5; j++){
if(chr[j] == word.charAt(i)){
answer += 1 + j * mul;
}
}
mul = (mul-1)/5;// 다음 자리로 넘어갈 때마다 가중치를 줄여줌.
}
return answer;
}
}
