8월 6일 99클럽 항해 16일

99클럽 항해 16일차

 

오늘의 문제는  모음 사전이다.

 

문제에서 주어지는 5개의 단어를 조합해서 단어의 순서를 반환하는 문제이다.

    -> 자리수마다 가능한 자리수 조합이 1, 5, 25, 125, 625로 5의 n^index임을 알 수 있다.

    -> 따라서 자리수 조합을 각 자리마다 합친 수가 다음 문자가 올때까지의 더해야되는 번호임을 알 수 있다.(기준 값은 word의 길이)

    -> {781(625+125+25+5+1), 156(125+25+5+1), 31(25+5+1), 6(5+1), 1}

    -> word 배열을 문자열 AEIOU와 비교하여 해당 단어가 몇 번째인지 수를 체크하고 정답을 구한다.

순으로 문제를 해결하였습니다.

 

class Solution {
    public int solution(String word) {
        String str = "AEIOU";
        int[] nums = {781, 156, 31, 6, 1};
        int answer = word.length();

        for (int i = 0; i < word.length(); i++) {
			int idx = str.indexOf(word.charAt(i));
            answer += nums[i] * idx;
        }
        return answer;
    }
}

 

하지만 문제에서는 dsf(깊이 우선 탐색)를 요구하는것같아서 다른 풀이로 풀어보려고 한다.

 

일부는 다른사람의 풀이를 참고했다.

 

    ->Treeset으로 문자열을 사전 순서로 정렬한다.

    ->dfs 알고리즘을 이용하여 길이가 최소1 최대 5인 문자열을 AEIOU다섯개로 조합할수 있는 문자열을 모두 저장한다

    ->TreeSet에서 word와 일치하는 문자열의 순서를 찾고, 일치하는 문자열이 있으면 그 위치를, 없다면 0을 반환한다.

import java.util.*;

class Solution {
    Set<String> set;
    String[] arr = {"A", "E", "I", "O", "U"};
    public int solution(String word) {
        int answer = 0;
        set = new TreeSet<>();

        for(int i = 0; i < 5; ++i) {
            dfs(arr[i],1);
        }
        int count = 0;
        for( String str : set) {
            count++;
            if(str.equals(word)) {
                return count;
            }
        }
        return answer;
    }
    public void dfs(String word, int depth) {
        set.add(word);
        if(depth == 5){
            return;
        }
        for(int i=0; i<5;++i){
            dfs(word+arr[i], depth+1);
        }
    }
}