(알고리즘 스터디) 2주차 금 _ 완전탐색🔎_ (Programmers) 모음사전

🌟 프로그래머스 / 완전탐색 / Level2 / 모음사전

📃 문제

프로그래머스

🚫 제한 사항

• word의 길이는 1 이상 5 이하입니다.
• word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

👀 입출력 예

word	result
"AAAAE"	6
"AAAE"	10
"I"	1563
"EIO"	1189

🤔 풀이 방법

1️⃣ 단어 생성 순서 이해

➡️ 먼저 단어의 생성 순서에 대해서 [A, B, C] 의 짧은 배열로 정리해보았다.

단어 생성 순서

그림을 그려보니 저번 피로도 문제와 유사하다는 것을 알 수 있었다. 피로도 문제의 경우 일반 순열(nPr)로서 visited 배열을 활용하여 중복을 피했다면, 이번 문제는 중복 순열(nΠr) 로 반대로 visited 배열을 사용하지 않고 돌리면 위 그림과 같은 순서로 출력이 가능하다.

따라서 핵심코드는

// arr 배열 : 기존 주어진 배열
// output 배열 : 결과값을 담는 배열
public void dfs (...) {
    if (depth == 최대깊이) {
        return;
    }
    for (int i=0; i<배열의 길이; i++ {
        output[depth] = arr[i];
        dfs(...); // 재귀 호출
    }
}

 으로 반대로 일반 순열보다 훨씬 간편해진 것을 알 수 있다.

 

2️⃣ 주어진 문자열과 중복순열의 결과값이 일치하는지를 확인하는 과정

➡️ 처음에는 문자열로 해결을 해보려고 했는데, 그렇게되면 depth 가 변화함에 따라 문자열을 substring 하는 과정이 머릿속에 잘 그려지지 않아서 주어진 문자열을 split 을 통해 한글자씩 배열에 담고, 중복순열의 매 단계 결과값인 배열 output 과 Arrays 의 내장함수인 equals를 활용해서 일치를 확인하는 방법을 사용했다.

Arrays.equals() 의 정의

💻 풀이 코드

import java.util.Arrays;

class Solution {
    public static String[] alphabet = {"A", "E", "I", "O", "U"}; // 모음
    public static String[] words; // 쪼개진 문자열을 담기위한 배열
    public static int answer = 0;
    public static boolean go = true;
    
    public int solution(String word) {
        // 주어진 문자열을 배열로 쪼개는 과정
        words = word.split("");
        
        dfs (0, new String[words.length]);
       
        return answer;
    }
    public static void dfs (String[] words, int depth, String[] output) {
        if (depth == 5) {
            return;
        }
        for (int i=0; i<5; i++) {
            // 필요한 내용만 담기위해 주어진 문자열 길이에 해당하는 만큼만 저장
            if (depth < words.length) {
                output[depth] = alphabet[i];
            }
            answer++;
            // 주어진 문자열과 일치하는지 확인
            if (depth == words.length-1 && Arrays.equals(words, output)) {
                go = false; // 해답을 찾으면 재귀를 멈춤
                break;
            }
            // 재귀
            dfs(depth+1, output);
            if (!go) { // 해답을 찾으면 재귀를 멈춤
                return;
            }
        }

    }
}

GitHub - Young998904/Practice_Algorithm_Auto: JAVA 알고리즘 저장소 🔥 (문제와 함께 자동 커밋)