프로그래머스 lv2 모음사전

문제 링크

모음 사전

풀이

• 두 가지 방법이 있는데, 하나는 제시된 문자열에 대한 규칙성 찾기, 하나는 dfs를 이용한 완전 탐색방법이다.
• 두 가지 모두 풀이해본다.

1. 문자열에 대한 규칙성 찾기

주어진 문자열에 대해서 규칙성에 맞게 써내려가다 보면 다음과 같은 규칙을 발견할 수 있다.

• 앞에서 5번째 자리의 문자열 변화는 +1 만큼 증가
• 앞에서 4번째 자리의 문자열 변화는 +6 만큼 증가
• 앞에서 3번째 자리의 문자열 변화는 +31 만큼 증가
• 앞에서 2번째 자리의 문자열 변화는 +156 만큼 증가
• 앞에서 1번째 자리의 문자열 변화는 +781 만큼 증가.

그니까 A, E, I, O, U 를 하나의 배열로 보고, 인덱스로 삼아서 그 수 만큼 증가율을 곱해서 더해주면 된다.

class Solution {
    public int solution(String word) {
        int answer = word.length();
        String aeiou = "AEIOU";
        int[] increaseARR = {781, 156, 31, 6, 1};

        for(int i = 0; i < word.length(); i++){
            answer += (aeiou.indexOf(word.charAt(i)) * increaseARR[i]);
        }

        return answer;
    }
}

그러나 이렇게 풀면 프로그래머스에서는 단 1점을 쥐어준다(...)

2. dfs를 이용해서 완전 탐색을 진행하는 방법

dfs를 이용해서 모든 문자열에 대해서 탐색을 진행하는 방법이다. 제시한 규칙성대로 모든 걸 구해본다.

모든 문자열을 탐색하고, 마지막에 그 문자열에 맞는 인덱스를 구하면 된다.

import java.util.List;

class Solution {
	List<String> list = new ArrayList<>();

    public int solution(String word) {
        dfs("", 0);
        return list.indexOf("AAAE");
    }
    
    public void dfs(String str, int len){
    	if(len > 5) return;
        list.add(str);
        for (int i = 0; i < 5; i++){
            dfs(str + "AEIOU".charAt(i), len + 1);
        }
    }
}

소감

• 아직도 완전탐색은 뭔가 어렵다.