[프로그래머스/Java] 모음사전(완전탐색 문제) 풀이

프로그래머스 알고리즘 고득점 Kit의 완전탐색 문제 중 하나인 '모음사전'을 자바로 풀어보았다. 

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

프로그래머스

 

 

 이 문제는 전에 대회나 코딩테스트에서 마주친 적이 있는 문제와 비슷했다. 그때는 이걸 완전탐색으로 접근할 생각을 못하고 규칙을 찾다가 예외가 너무 많아서 포기했는데, 알고 보니 완전탐색 문제였다. 완전탐색 문제라는 걸 인지하고 나니, 모든 경우의 수를 만드는 게 관건이지, 조건을 체크하는 건 크게 어렵지 않았다. 

 그래서 완전탐색으로 이 문제를 해결한 방법은 "AEIOU"로 만들 수 있는 모든 Stirng의 경우의 수를 만들고, 이를 정렬하여 주어진 word의 위치를 찾는 것이었다. 가장 어려운 부분은 "AEIOU"로 만드는 모든 String의 경우의 수를 만드는 부분이었다. 내가 선택한 방법은 첫 번째 글자부터 5개의 글자를 순회하면서 하나씩 넣는 방법이었다. 그래서 getWord라는 recursive method를 사용하여 만들었고, 다 만들어진 set을 sort 해서 String array로 변환해 줬다. 여기서 set을 그대로 사용하지 않고 string array를 사용해 준 이유는 index에 접근하여, word가 몇 번째 단어인지를 찾아야 하기 때문이다. 

import java.util.*;

class Solution {
    public void getWords(String prefix, Set<String> set, String alphabet) {
        if (prefix.length() != 0) set.add(prefix);
        if (prefix.length() >= 5) return;
        
        for (char c : alphabet.toCharArray()) {
            getWords(prefix+c, set, alphabet);
        }
    }
    
    public int solution(String word) {
        String alphabet = "AEIOU";
        Set<String> set = new HashSet<>();
        getWords("", set, alphabet);
        String[] dictionary = set.stream().sorted().toArray(String[]::new);
        for (int i = 0; i < dictionary.length; i++) {
            if (dictionary[i].equals(word)) return i+1;
        }
        
        return 0;
    }
}

 

 

 

 이렇게 완전탐색으로 풀고 나서, 그래도 뭔가 규칙을 찾아서 더 효율적으로 풀이할 수 있을 것 같다는 생각이 들었다. 그래서 고민하다가 나한테서는 답이 안 나와서 다른 분들의 풀이를 확인했더니, 역시나 수학적으로 접근하여 상당히 효율적으로 풀 수 있는 방법이 있었다. 우선 전체 경우의 수를 total에 저장해 두고, 이걸 가중치로 사용한다. 몇 번째 자리에 나왔는가에 따라서 순서에 미치는 영향이 다르다. 앞쪽에 나올수록 순서에 영향에 미치는 영향이 크므로, 더 큰 값을 곱해주고, 그리고 뒤로 갈수록 total을 5로 나눠가면서 작은 가중치를 적용한다. 인덱스가 0 기반이니까, answer에 더해줄 때, 즉 순서를 구해줄 때는 1을 더해줘야 한다. 

 "EI"를 예로 들면 과정은 아래와 같다. 

입력 데이터: "EI"
(1) "E"의 순서 : E의 인덱스(1) * 781 + 1 = 782번째
(2) "EI"의 순서 : 782 + I의 인덱스(2) * 156 + 1 = 4905

import java.util.*;

class Solution {
    public int solution(String word) {
        int total = 0;
        for (int i = 1; i <= 5; i++) {
            total += Math.pow(5, i);
        }
        
        int answer = 0;
        for (String s : word.split("")) {
            total /= 5;
            answer += "AEIOU".indexOf(s) * total + 1;
        }
        
        return answer;
    }
}