[프로그래머스,자바] Level2: 위클리 챌린지 5주차 [모음 사전]

문제분석

문제는 A , E, I, O, U 로만 쓰여있는 사전낱말중에서 특정 단어가 몇번째 위치하는지 구하는 문제다.

 

무엇을 구해야하는지는 명확하니 구현으로 넘어가겠다.

문제풀이

 

딱 이문제를 보고 생각한게, 단어를 이루는 문자가 5개니깐 

5중반복문이나, 완전탐색(DFS,BFS)으로 전부 탐색하면 되는거 아닌가?

 

모든 경우를 도는 횟수는 계산해보면 연산을 각 단어만다 최대 3905번을 탐색한다. {UUUUU=3905}

 

하지만 ,매번 들어오는 단어마다 최대 3905번 반복하는건 너무 비효율적이지 않나?  

 

그래서 규칙을 곰곰히 생각해봤다. 

 

먼저 3번째 예시인 "I" 의 위치값을 보자, 1563이다.

그렇다면, "I" 이전에 지나온 낱말수는 1562개란뜻이다. 지나온 낱말수는 총 2개

즉, 맨 앞자리의 문자가 바뀔때마다 781낱말만큼 넘긴다!

 

그다음으로, "EIO"의 위치값을 보자, 1189이다.

3번 예시를 활용해,  첫번째자리 알파벳은 E다. E 이전엔 A라는 단어가있었으므로 781낱말만큼 넘긴다.

 

여기서 중요하다!  781낱말만큼넘겼으니 E의 자리는 781+1이다. 즉, 782번째다. 

 

자리가 바뀔때마다 이전에 지나온 낱말수+1 이 해당 단어의 위치다.

 

E의 자리는 782번째다. 그러면, EI의 자리는 몇번째일까?

 

같은원리로 간단하다. 781에서 1을빼고, 5로 나누면 156이다. 즉, 2번째자리는 156낱말만큼 넘긴다!

 

따라서, EI는 782+156*2+1=1095다.

 

같은 원리로 EIO를 구해보자. 156에서 -1을한뒤, 5로 나누면 31이다. 즉 3번째자리는 31낱말만큼 넘긴다!

 

따라서, EIO는 1095+31*3+1=1189다. 

 

 

여기까지 풀이를 보았을때 이런생각 해봤을것이다. 아니 왜 -1을하고 5로 나누지?? 

 

그건 바로, 빈칸때문이다. 빈칸이 있는경우도  낱말로 치기때문에 +1만큼 차이가 나는것이다. EX) E, EIO,AAE

 

 

긴 설명은 끝이다 이젠 코드로 구현해보자.

 

class Solution {
    public int solution(String word) {
        int answer = 0;
 
        String[] alpha = {"A","E","I","O","U"};
 
        int[] past_words = {781,156,31,6,1};
 
        String[] temp = word.split("");
 
        for(int i=0;i<temp.length;i++){
            for(int j=0;j<alpha.length;j++){            
                if(temp[i].equals(alpha[j])){
                    answer+=past_words[i]*j+1;break;
                }
            }
        }
 
        return answer;
    }
}

이전에 지나온 낱말수를 past_words 배열로 구현했다.

 

그리고 사전이 지니고있는 단어를 alpha 배열로 저장했다.

 

word의 낱말을 한단어씩 쪼개어서 temp로 저장한뒤,  AEIOU인지 확인한다.

 

규칙에 의해, 이전에 지나온 낱말수*지나온낱말갯수 +1을 해준다.

 

 

이렇게 구현하면 한 단어당 최대 25번의 연산만하면 된다!

 

3905번의 연산보다 25번의 연산으로 꽤나 효율적으로 코딩이되었다! 

 

실제로 완전탐색으로 푼 다른사람 풀이를 보면 코드는 길고 연산속도는 이 코드보다 약 20배느리다.