99클럽 코테 스터디 9일차 TIL - 완전탐색

항해99 코테 스터디 9일차 문제인 프로그래머스의 '모음사전'은 모음만을 이용하여 단어 사전을 만들었을 때, 특정 단어의 순서를 구하는 문제다. 난이도는 레벨2이며 완전탐색을 통해 해결할 수 있다.

 

오늘의 문제 - 모음사전 문제 정보

문제 키워드

- 완전탐색

난이도

- Level 2

 

문제 요약

• 모음 A, E, I, O, U만을 이용해 최대 5글자의 단어 사전을 만들었다. (A ~ UUUUU)
• 이 때, 타겟 단어의 순서를 구하라.
• ex) AAAAE=6, I=1563

 

문제 풀이 과정  

• 5글자로 5자리까지 만들 수 있으므로 최대 글자수는 5^5개가 된다. 따라서 완전 탐색을 이용할 수 있다.
• DFS를 이용하여 단어를 사전 순서대로 하나씩 만들어가다, 타겟 단어를 발견하면 종료하고 순서를 반환한다.

코드

import java.util.*;

class Solution {
    
    String[] alp = {"A", "E", "I", "O", "U"};
    List<String> dict = new ArrayList<>();
    Boolean hasAnswer = false;
    
    public int solution(String word) {
        hasAnswer = false;
        dfs("", word);
        return dict.size();
    }
    
    public void dfs(String now, String target) {
    	// 타겟 단어를 찾으면 탐색을 멈춘다.
        if (now.equals(target)){
            hasAnswer = true;
        }
        
        if (hasAnswer) return;
        
        dict.add(now);
        
        // 현재 단어에 알파벳을 하나씩 추가하며 탐색한다.
        if (now.length() < 5) {
            for(int i=0; i<5; i++) {
                String next = now + alp[i];
                dfs(next, target);
            }
        }
        
    }
}

• 시간복잡도: O(N) → N: 최대 단어 개수
• 공간복잡도: O(N)

 

오늘의 학습 회고

• 처음 구현 시에는 사전을 끝까지 구축한 다음에 사전에서 타겟 단어의 순서를 찾았다.
• 하지만 타겟 단어를 찾은 후에는 사전을 더 만들 필요가 없으므로 탐색을 멈추도록 수정하였다.