프로그래머스 - 모음 사전

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

프로그래머스

 

 

 

 

 

문제

• 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록
• 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU”
• 단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return

 

입출력 예

• word : "AAAAE"
• result : 6

 

 

풀이

• 주어진 모음을 여러 개 선택해서 배치해야 하기 때문에 중복 순열을 쓴다. 
  • 5Π1, 5Π2, 5Π3, 5Π4, 5Π5을 각각 구한다.
  • N이 5로 작아서 순열을 써도 시간 초과가 나질 않는다.
• 중복 순열의 결과를 ArrayList에 담는다.
  • 중복되는 결과 없으므로 HashSet을 굳이 쓸 필요 없다.
• ArrayList에 담긴 문자열들을 사전순으로 정렬한다(오름차순 정렬)
• 리스트를 순회하며 word가 사전에서 몇 번째 단어인지 카운팅한다.

 

 

 

 

 

코드

import java.util.*;

class Solution {
    static String[] vowels = {"A", "E", "I", "O", "U"};
    static String[] result;
    static List<String> list;
    
    public int solution(String word) {
        list = new ArrayList<>();
        
        for(int i = 1; i <= 5; i++) {
            result = new String[i];
            puermutation(0, i, word);
        }
        
        Collections.sort(list); //정렬

        //이 단어가 사전에서 몇 번째 단어인지 카운팅
        int answer = 1;
        for(String str : list) {
            if(str.equals(word)) {
                break;
            }
            answer++;
        }
        
        return answer;
    }
    
    public void puermutation(int depth, int num, String word) {
        if(depth == num) {
            //완성된 단어 저장
            String voca = "";
            for(String str : result) {
                voca += str;
            }
            
            list.add(voca);
            
            return;
        }
        
        for(int i = 0; i < 5; i++) {
            result[depth] = vowels[i];
            puermutation(depth + 1, num, word);
        }
    }
}

 

 

 

 

 

결과

 

 

 

 

 

배운점