99클럽 코테 스터디 16일차 TIL , 모음사전

문제

풀이

"A", "E", "I", "O", "U"로 이루어진 문자 사전이 있다.

오름차순으로 정렬되어 있다.

입력으로 단어가 주어졌을 때 몇번째에 값이 있는지 확인해서 몇 번째에 있는지 return 하면 된다.

 

풀이 1 - 정답

import java.util.*;
class Solution {
    public int solution(String word) {
        int answer = 0;
        String[] alpha = {" ","A","E","I","O","U"};
        StringBuilder sb = new StringBuilder();
        Set<String> set = new TreeSet<>();
        for(int a=5;a>=0;a--){
            for(int b=5;b>=0;b--){
                for(int c=5;c>=0;c--){
                    for(int d=5;d>=0;d--){
                        for(int f=5;f>=0;f--){
                            String str = (alpha[a] + alpha[b] + alpha[c] + alpha[d] + alpha[f])
                            		.replaceAll(" ", "");
                            if(str.equals("")) continue;
                            set.add(str);
                        }
                    }
                }
            }
        }


        for (String s : set) {
            if(s.equals(word)) break;
            answer++;
        }

        return answer+1;
    }
}

 

무식하게 풀이했다.

A,E,I,O,U 사전을 중복을 제거하여 만든다.

해당 인덱스를 찾아서 1추가 하여 return 하면 완료.

풀이 2 - 정답

class Solution {
    static String[] alpha = {"A","E","I","O","U"};
    static int answer = 0;		
    static boolean flag = false;	//찾았는지
    static String inputWord;

    public int solution(String word) {
        inputWord = word;
        dfs("",0);
        return answer;
    }

    private void dfs(String str, int depth) {
        if(depth > 5 || flag) return;	//찾았거나 depth가 5보다 크면

        if(str.equals(inputWord)) {		//찾으면 flag바꿔주고
            flag = true;
            return;
        }

        answer++;
        for(int i=0;i<5;i++){
            dfs(str + alpha[i], depth + 1);
        }
    }
}

 

dfs를 활용해서 풀이했다. 

위에 완탐을 사용했을 경우보다 훨씬 빠르게 찾았다.

TIL

• 완전탐색
• 항해 리부트 코스 참여했다.