[Programmers / Level 2] 84512. 모음사전 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/84512
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/모음사전

입출력 조건

입출력 예시

문제 이해

• 주어진 모음(A, E, I, O, U)으로 만들 수 있는 모든 단어를 사전순으로 정렬했을 때, 특정 단어가 몇 번째인지 찾는 문제

알고리즘

풀이 시간 : 25분

• DFS로 단어 생성
  • 빈 문자열 -> "A", "E", "I", "O", "U"를 하나씩 추가해 단어 만들기
  • 최대 5글자(count 증가)
• 목표 단어(word)를 찾으면 -> 종료
  • 생성한 단어가 word와 같다면 -> answer를 count 값으로
• word를 찾으면 바로 return

import java.util.*;

class Solution {
    static String[] words = {"A", "E", "I", "O", "U"};
    static int count, answer;
    
    public int solution(String word) {
        count = 0;
        answer = 0;
        dfs("", word, 0);
        return answer;
    }

    static void dfs(String str, String target, int len) {
        if (str.equals(target)) {
            answer = count;
            return;
        }
        if (len == 5) return;
        
        for (int i = 0; i < 5; i++) {
            count++;
            dfs(str + words[i], target, len + 1);
            if (answer > 0) return;
        }
    }
}

결과