모음사전

Problem. 모음사전

---

Link.

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

코딩테스트 연습 - 모음사전

---

Description.

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용할 수 있는, 길이 5이하의 모든 단어가 수록되어 있습니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 작성하세요.

 

※ 제한사항

• word의 길이는 1 이상 5 이하이다.
• word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있다.

 

입출력 예시

 

---

Approach. 

1) 모든 문자열을 생성하고 사전식으로 정렬하여 매개변수 word를 indexOf 메소드로 찾기 (간단하고 무식한 방법!)

• DFS 방식으로 모든 경우의 수를 고려하여 문자열을 생성해 배열에 삽입
• 이후 sort 메소드를 사용하여 배열내 요소들을 사전식으로 정렬
• 정렬된 배열에서 indexOf 메소드를 사용해 매개변수 word의 위치를 찾아냄 (인덱스)
• 배열의 인덱스가 0부터 시작했으므로 찾아낸 인덱스에 1을 더해 최종적으로 반환!

 

2) 규칙을 찾아서!

 

모든 경우의 수를 먼저 살펴보자

① 문자열 5자리: 5×5×5×5×5 = 3125

② 문자열 4자리: 5×5×5×5 = 625

③ 문자열 3자리: 5×5×5 = 125

④ 문자열 2자리: 5×5 = 25

⑤ 문자열 1자리: 5 = 5

 

따라서 모든 문자열의 개수는 아래와 같다:3125 + 625 + 125 + 25 + 5 = 3905

 

본격적으로 규칙을 찾아보자!

- 문자열 5번째 자리가 바뀌는 경우: 1씩 바뀐다

AAAAA = 5

AAAAE = 6

AAAAI = 7

AAAAO = 8

AAAAU = 9

 

3905/3125 = 1.25 

Math.floor(3905/3125) = 1

 

문자열 5번째가 바뀌는 경우

 

- 문자열 4번째 자리가 바뀌는 경우: 6씩 바뀐다

AAAA = 4

AAAE = 10

AAAI = 16

AAAO = 22

AAAU = 28

 

3905/625 = 6.25

Math.floor(3905/625) = 6

 

문자열 4번째가 바뀌는 경우

 

- 문자열 3번째 자리가 바뀌는 경우: 31씩 바뀐다

AAA = 3

AAE = 34

AAI = 65

AAO = 96

AAU = 127

 

3905/125 = 31.24

Math.floor(3905/125) = 31

 

문자열 3번째가 바뀌는 경우

 

마찬가지로 문자열 2번째와 1번째 경우를 구해보면 각각

 

3905/25 = 156.2

Math.floor(3905/25) = 156

 

3905/5 = 781

Math.floor(3905/5) = 781

 

위의 규칙을 종합해보면,

각 자리수가 바뀌는데 필요한 횟수를 각각 구한 후 

모두 더해주면 우리가 원하는 답이 나온다!

 

프로그래머스 입출력 예시로 위의 규칙이 맞는지 확인해보자!

#1. word = "AAAE"

첫번째 자리수 A이므로: +1

두번째 자리수 A이므로: +1

세번째 자리수 A이므로: +1

네번째 자리수 E이므로 A에서 한번 바뀌었다: (6×1)+1=7

 

총합: 1+1+1+7 = 10

 

#2. word = "I"

첫번째 자리수 I이므로 A에서 두번 바뀌었다: (781×2)+1=1563

 

총합: 1563 = 1563

 

#3. word = "EIO"

첫번째 자리수 E이므로 A에서 한번 바뀌었다: (781×1)+1=782

두번째 자리수 I이므로 A에서 두번 바뀌었다: (156×2)+1=313

세번째 자리수 O이므로 A에서 세번 바뀌었다: (31×3)+1=94

 

총합: 782+313+94 = 1189

 

---

My Answer. 

1) 모든 문자열을 생성한 방법

function solution(word) {
    
    let answer = [];
    let list = ['A', 'E', 'I', 'O', 'U']
    
    // 만들어진 문자열을 stack에 쌓는다
    const dfs = (list, depth, num, arr) => {
        if(depth === num) {
            answer.push(arr.join(""))
            return
        }         
        else {
            for(let i = 0; i < 5; i++) {
                arr.push(list[i])
                dfs(list, depth + 1, num, arr)
                arr.pop()
            }
        }
    }
        
    for(let i = 1; i <= 5; i++) {
        dfs(list, 0, i, [])
    }
    
    return answer.sort().indexOf(word) + 1
}

 

2) 규칙을 찾아 구현한 방법

function solution(word) {
    let match = {
        A: 0,
        E: 1,
        I: 2,
        O: 3,
        U: 4,
    }
    return word.split("").reduce((acc, cur, idx) => acc + match[cur]*[781, 156, 31, 6, 1][idx] + 1, 0)
}

 

---

References.

https://velog.io/@cjh951114/JavaScriptProgrammers-%EB%AA%A8%EC%9D%8C-%EC%82%AC%EC%A0%84

[JavaScript][Programmers] 모음 사전

https://jinn2u.tistory.com/9

[프로그래머스] 모음 사전 js 풀이

https://programmers.co.kr/questions/25140

프로그래머스