문제 출처

코딩테스트 연습 > 완전탐색 > 모음사전
https://school.programmers.co.kr/learn/courses/30/lessons/84512

문제 설명

알파벳 모음 'A','E','I','O','U'만을 사용하는 길이 5이하의 모든 단어가 수록되어있을 때, 단어 word가 주어질 때, word가 몇 번째 단어 인지 return 하라

접근 방법

2단계를 이용하여 접근했다.

1. 조합을 전부 만들어 PriorityQueue에 모든 조합을 삽입한다.
2. HashMap에 등록 하여 단어를 검색하면 그 결과가 나오게 한다.

import java.util.*;

class Solution {
    
    static PriorityQueue<String> pq = new PriorityQueue<>();
    static String[] arr = {"A", "E", "I", "O", "U"};
    
    public void permute(String str, int depth){
        if(depth == 5){
            return;
        }
        
        for(int i = 0; i<arr.length; i++){
            String s = str + arr[i];
            pq.add(s);
            permute(s, depth +1);
        }
    }

    public int solution(String word) {
        int answer = 0;
        HashMap<String,Integer> hm = new HashMap<>();
        
        permute("", 0);
        
        int index = 1;
        while(!pq.isEmpty()){
            hm.put(pq.poll(), index++);
        }
        
        answer = hm.get(word);
        return answer;
    }
}

Review
DFS를 이용한 접근으로, DFS를 통해 조합을 만들 때, 그 조합이 확인하고자 하는 word에 도달하면 해당 count를 num에 대입하는 방식이다.

import java.util.*;

class Solution {
    
    static String arr[] = {"A", "E", "I", "O", "U"};
    static int num = 0, count = 0;
    
    public void dfs(String word, String str, int depth){
        
        if(depth > 5){
            return;
        }
        if(str.equals(word)){
            num = count;
            return;
            }
        count++;
        for(int i =0 ; i<arr.length; i++){
            String s = str + arr[i];
            dfs(word, s, depth+1);
            
        }
    }
    
    public int solution(String word) {
        dfs(word, "", 0);
        return num;
    }
}

알게된 점

PriorityQueue는 문제에서 원하는 방식으로 정렬을 할 수 있다. 정렬을

1. A,E,I,O,U 순서대로 우선 순위를 잡는다.
2. 길이가 길 수록 뒤로 우선 순위를 잡는다.

두 가지 조건을 통해 PriorityQueue를 사용하여 풀 수 있다.
하지만 이는 시간 복잡도가 추가 된다는 단점이있다.

해당 문제는 DFS로 풀 수 있다.
내일은 DFS로 풀어보면서 접근해야겠다.

Reivew

문제는 빠르게 풀었으나, count 제대로 생각하지 않아서 삽질하느라 꽤나 오랜시간이 걸렸다. 반성해야겠다.

문제푼 흔적