카카오 코테도 끝났으니 오늘은 오랜만에 밀린 위클리 챌린지를 풀어보았다.
오늘 푼 문제는 위클리 챌린지 5주차 - 모음사전이다 !
이 문제를 풀면서 생각난김에 순열, 중복순열, 조합, 중복조합 총정리 ! 글을 작성해 보았다. 풀이 방법부터 간단하게 말해보자면 중복 순열 문제이다 ! 그러므로 잘 모른다면 한 번 읽어보고 문제를 푸는 것 추천 !
문제 설명
사전에 알파벳 모음 '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 |
풀이 방법
맨 처음에 문제를 읽고 순서가 진짜 사전순, 즉 스트링을 그냥 정렬한 거랑 똑같은건지 명확하게 이해가 안 갔다. 설명과 예시를 봐도 뭔가 헷갈렸던.. 그치만 설명에 [ 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다. ] 라고 밖에 설명이 안 되어 있으니 그러면 기본 사전순이겠구나 생각하고 문제를 풀었다.
풀이 방법은 아래와 같다.
- 다섯 모음 알파벳으로 만들 수 있는 길이 1-5인 모든 문자열을 만들어 리스트에 넣는다. > 중복순열🔥
- 리스트를 정렬한다. ( 스트링 기본 정렬하면, 사전순으로 정렬된다. )
- 주어진 단어가 리스트의 몇 번째에 위치하는지 구해서 1을 더해서 반환해준다.
1번 과정에서 중복 순열을 사용하는 것이 이 문제의 핵심이었던 것 같다. 따라서 중복 순열을 구할 수만 있다면 쉽게 풀 수 있는 문제였을 것이다 !
코드
import java.util.*;
class Solution {
public static char[] alpha = {'A', 'E', 'I', 'O', 'U'};
public static ArrayList<String> dic = new ArrayList<>();
public static void combination(char[] out, int depth, int r){
if(depth == r){
dic.add(new String(out));
return;
}
for(int i=0; i<alpha.length; i++){
out[depth] = alpha[i];
combination(out, depth+1, r);
}
}
public int solution(String word) {
for(int i=1; i<=alpha.length; i++){
combination(new char[i], 0, i);
}
Collections.sort(dic);
return dic.indexOf(word)+1;
}
}