[Java] 프로그래머스 모음사전

1. 문제분석

알파벳 모음으로 길이 5이하의 단어를 만든다고 한다. 그 때 주어진 word는 몇번째 있는지 찾는 문제다.

헷갈리면 안되는것은 AAAAA, AAAAE 처럼 만들어진다고 해서 그냥 배열에 모음 4개씩, 총 25개 넣으면 난리가 난다.

 

문제는 길이 5 이하의 단어다. 그렇다면 바로 중복 부분수열을 통해서 구하면 된다

A가 5개 있어도 상관없고 E가 5개 있어도 상관없다. 주어진 5개의 단어로 길이 5이하의 모든 부분 수열을 구하면 된다.

2. 구현

import java.util.ArrayList;
import java.util.Comparator;

public class Solution {

    ArrayList<String> list = new ArrayList<>();

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.solution("EIO"));
    }

    public int solution(String word) {
        int answer = 0;
        char[] arr = {'A', 'E', 'I', 'O', 'U'};
        perm(arr, new char[arr.length], 0, arr.length);
        list.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        });

        for(int i = 0; i<list.size(); i++){
            if(list.get(i).equals(word)){
                answer = i+1;
                break;
            }
        }
        return answer;
    }

    public void perm(char[] arr, char[] output, int depth, int n) {
        if (depth >= 1 && depth <= 5) {
            String temp = "";
            for (int i = 0; i < depth; i++) {
                temp += output[i];
            }
            list.add(temp);
        }
        for (int i = 0; i < n; i++) {
            if(depth == 5){
                return;
            }
            output[depth] = arr[i];
            perm(arr, output, depth + 1, n);
        }
    }
}

필자는 순열구하는 코드를 살짝 수정했다.

기존의 visited배열로 방문 여부를 구해 중복을 없앴다면 visited 배열을 없애서 사용했다.

 

또한, 길이는 5이하의 문자이므로 1 ~ 5일때 출력하면 된다.

하지만 for문 내부의 depth가 5인 경우, 즉 6개를 뽑을려고 할때는 return을 해줬다.

 

나머지는 depth에 따라 코드를 출력하면 된다.

3. 마무리

예전에 중복순열에 대해 잠깐 본 적이 있어 금방 해결한 문제다.

처음은 모음을 각자 5개로 순열을 구했는데 문제보니 길이가 5이하여서 머쓱했다..