[TIL] 99클럽 코테 스터디 7일차 TIL + 프로그래머스 모음사전

 

 

문제 풀이

프로그래머스 모음사전

 

문제 탐색하기

DFS 알고리즘을 활용하여 풀이 설계하기

깊이 우선 탐색 알고리즘에 대해서는 아래의 게시글에 개념을 설명해두었습니다.

https://coding-babo.tistory.com/151

[TIL] 99클럽 코테 스터디 4일차 TIL + 백준 24479 깊이 우선 탐색 1

 

DFS는 스택 자료 구조를 사용하여 구현할 수도 있고 재귀호출을 통해 구현할 수도 있습니다.

프로그래머스의 모음사전 문제는 재귀호출을 통해 DFS를 구현하였고 완전탐색을 통해 모음사전을 단어리스트를 모두 저장한 뒤에 원하는 단어의 index를 찾는 방향으로 문제를 설계했습니다.

 

모음사전의 단어들은 A, E, I, O, U 로만 이뤄지는 최대 5글자의 단어들로 구성되어있습니다.

이 모음들을 정점이라고 생각하고 A를 방문했다면 그 다음 방문할 수 있는 모음을 방문하고 이렇게 단어가 5글자가 될때까지 탐색에 들어갑니다. 그 과정에서 단어리스트에 계속해서 단어들을 저장해줍니다. 

더이상 탐색할 수 없다면 백트래킹하여 다음 모음을 탐색하는 과정을 반복하면 주어진 모음으로 이루어진 모음사전을 완성할 수 있습니다.

 

그 후 찾으려는 단어의 인덱스에 1을 더한값을 출력하면 답을 구할 수 있습니다.

 

문제 풀이

import java.util.ArrayList;

class Solution {
    
    static char[] alphabet = {'A', 'E', 'I', 'O', 'U'};
    static ArrayList<String> wordList = new ArrayList<>();
    
    public int solution(String word) {
        
        StringBuilder sb = new StringBuilder();
        makeWord(0, sb);
        return wordList.indexOf(word)+1;
    }
    
    private static void makeWord(int idx, StringBuilder sb){
        int temp = idx+1;

        for(int i=0; i<5; i++){
            sb.append(alphabet[i]);
            wordList.add(sb.toString());
            if(sb.length() < 5){
                makeWord(temp, sb);
            }
            sb.setLength(idx);
        }
    }
}

 

 

오늘의 회고

오늘의 문제는 DFS 알고리즘을 활용하면 풀 수 있었던 문제였는데 비슷한 방식으로 풀었지만 풀면서도 DFS라고는 생각하지 못했던 것이 아쉬웠습니다. 좀 더 문제를 많이 풀어서 아이디어를 빨리 캐치하는 능력을 키우고 싶습니다. 흑흑...