[프로그래머스 알고리즘 고득점 Kit][완전탐색][Java] 모음사전

https://school.programmers.co.kr/learn/courses/30/lessons/84512

프로그래머스

 

풀이 방법

• DFS로 A,E,I,O,U를 사전순으로 조합해가며 문자열 생성
• 문자열이 하나 완성될 때마다 cnt++
• target과 일치하면 found = true로 표시하고 탐색 중단

 

class Solution {
    char[] alphabets = {'A', 'E', 'I', 'O', 'U'};
    int cnt = 0;
    boolean found = false;
    
    public int solution(String word) {
        dfs(new StringBuilder(), word);
        return cnt;
    }
    
    public void dfs(StringBuilder sb, String target) {
        if(found) return;
        if(sb.length() == 5) return;
        
        for(int i=0; i<alphabets.length; i++) {
            sb.append(alphabets[i]);
            cnt++;
            if(target.equals(sb.toString())) {
                found = true;
                return;
            }
            dfs(sb, target);
            if(found) return;
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

배운 점

• 사전순 나열은 알파벳 배열을 순서대로 순회하는 DFS로 자연스럽게 구현됨
• deleteCharAt(idx): 문자 하나만 삭제 (delete(start,end)는 범위 삭제라 인자 2개 필요)
• 재귀 호출 후 found 체크를 안 하면, 정답을 찾은 뒤에도 다른 분기를 계속 탐색해 cnt가 잘못 커짐 → 재귀 호출 직후 반드시 found 체크 필요
  
  
  

조건문을 조금 더 깔끔하게 한다면.

private void dfs(StringBuilder sb, String target) {
    if (found) return;
    if (sb.length() == 5) return;

    for (int i = 0; i < alphabets.length && !found; i++) {
        sb.append(alphabets[i]);
        cnt++;
        if (sb.toString().equals(target)) {
            found = true;
        } else {
            dfs(sb, target);
        }
        sb.deleteCharAt(sb.length() - 1);
    }
}