[Day07]JAVA- 프로그래머스 모음사전

 

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

프로그래머스

프로그래머스 모음사전 문제를 풀기 위해서는 완전탐색에 대해서 알아야 한다. 

 

완전탐색이란

모든 경우의 수를 시도하는 방법으로 입력 값의 범위가 작은 경우에 주로 사용된다. 

 

* 완전탐색 알고리즘 

- 단순 Brute-Force 
: 단순히 반복문과 조건문으로 모든 경우를 만들어 답을 구하는 방법

- 비트 마스트(Bitmask)
: 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나 , 포함되지 않은 두 가지 선택으로 구성되는 경우

- 재귀함수 
: 종료점에 도달할 때까지 반복적으로 자기자신을 호출하는 방법

- 순열
: 서로 다른 N개를 일렬로 나열하는 방법
순열의 경우의 수는 N!으로 완전 탐색을 이용하기 위해서는 N이 한자리 수는 되어야 함

- BFS , DFS
: BFS 는 너비우선탐색 으로 하나의 요소를 방문하고 그 요소에 인전합 모든 요소를 우선 방문하는 방식
: DFS 는 깊이우선탐색 으로 노드의 자식노드로 탐색하는 방식이다

 

어떠한 알고리즘이 적합할지 문제 파악이 제일 중요하다고 보면 된다.

 

모음사전 문제는 길이가 5 이하의 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는 단어를 모두 만드는 것이 포인트인다. 

 

문자의 규칙을 파악해야한다. 

 

A E I O U 순서로 단어 만들기 

1 A
2 AA
3 AAA
4 AAAA

------------
5 AAAAA
6 AAAAE
7 AAAAI
8 AAAAO

9 AAAAU

------------
10 AAAE
11 AAAEA
12 AAAEI
.

.

------------

16 AAAI

 

 

다섯번째 자리는 문자가 바뀔때마다 1씩 증가 
네번째 자리는 문자가 바뀔때마다 (1*5) + 1 = 6씩 증가
세번째 자리는 문자가 바뀔때마다 (6*5) + 1 = 31씩 증가 
두번째 자리는 문자가 바뀔때마다 (31*5) + 1 = 156씩 증가
첫번째 자리는 문자가 바뀔때마다 (156*5) + 1 = 781씩 증가 

 

단어의 길이를 구하고 위치마다 몇번이 바뀌어야 해당 문자가 올 수 있는지 for문을 돌려 찾는다.

 

*최종코드

class Solution {
    public int solution(String word) {
         int answer = 0;
        String str = "AEIOU";
        int[] x= {781,156,31,6,1};
        
        answer = word.length();
        
        for(int i=0;i<word.length();i++)
        {
            char c = word.charAt(i);
            int idx = str.indexOf(c);
            answer += x[i]*idx;
            
        }
       
        return answer;
    }
}