[99클럽 코테 스터디 1일차 TIL] DFS

📖 오늘의 학습 키워드
DFS

오늘의 회고

문제

[모음 사전]
https://school.programmers.co.kr/learn/courses/30/lessons/84512

나의 해결

import java.util.*;
class Solution {
    public String[] alphabets = {"A", "E", "I", "O", "U"};
    public List<String> list;
    public int solution(String word) {
        list = new ArrayList<>();
        int answer = 0;
        dfs("", 0);
        for(int i = 0; i < list.size(); i++) {
            if(list.get(i).equals(word)){
                answer = i;
                break;
            }
        }
        return answer;
    }
    public void dfs(String s, int len) {
        list.add(s);
        if(len == 5){
            return;
        }
        for(int i = 0; i < 5; i++) {
            dfs(s+alphabets[i], len+1);
        }
    }
}

완전 탐색이라는 키워드와 문제를 보고 바로 DFS를 떠올렸다.

DFS로 사전에 들어갈 단어의 모든 경우의 수를 구하고 이를 list에 저장한다. 문제에 길이 5 이하의 모든 단어라는 조건이 있어 문자열의 길이가 5가 되면 탐색을 중단하고 돌아온다.

list의 저장 순서가 사전의 순서와 동일하기 때문에 탐색이 끝나면 list를 순회하여 word와 동일한 문자열의 인덱스를 찾아 반환한다.

새로 학습한 내용

위 문제를 해결하면서 DFS를 복습할 수 있었다.

문제를 풀고 난 후 이렇게 모든 경우의 수를 구하지 않고도 해결할 수 있는 방법이 있을 것 같았다. 그래서 찾아보니 자리마다 알파벳이 바뀔 때 증가하는 값이 같아 이를 활용하면 단어의 순서를 바로 구할 수 있다는 것을 알게 되었다.

class Solution {
    public int solution(String word) {
        String alphabets = "AEIOU";
        int[] nums = {781, 156, 31, 6, 1};
        int answer = word.length();
        for (int i = 0; i < word.length(); i++) {
            answer += nums[i] * alphabets.indexOf(word.charAt(i));
        }
        return answer;
    }
}

이 풀이로 다음과 같이 실행 시간을 단축시킬 수 있었다.
앞으로는 이처럼 실행 시간을 단축하는 풀이를 스스로 고안해 내고 싶다!