on
Lv_2. 모음사전
Lv_2. 모음사전
* Programmers _위클리 챌린지 5주차 문제입니다.
* 언어는 javascript 를 선택했습니다.
1. 문제
1) 모음사전
사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.
단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.
2) 제한사항
word의 길이는 1 이상 5 이하입니다.
word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.
2. 알고리즘! 생각해보자
처음에는 문제가 이해가지 않아 주르륵 나열해보니
약간의 규칙을 찾을 수 있었습니다.
1: A <-> 781 782(=1+781): E 2: AA <-> 156 158(=2+156): AE 3: AAA <-> 31 34(=3+31): AAE AAI AAO AAU 4: AAAA <-> 6 10(=4+6): AAAE AAAI AAAO AAAU 5: AAAAA <-> 1 6: AAAAE 7: AAAAI 8: AAAAO 9: AAAAU
word는 1~5자리인데, _ _ _ _ _ 각 자리수 별로
첫번째 자리는 781
두번째 자리는 156
세번째 자리는 31
네번째 자리는 6
다섯번째 자리는 1
씩 차이가 나는 것을 확인할 수 있었습니다.
그런데 입출력 예시와 값을 비교해보면, 위의 값 만으로는 해결되지 않는 것을 확인할 수 있습니다.
예를들어, "EIO" 의 경우 1189 이 출력되어야 하는데,
위의 값으로 계산하면, (781 * 1) + (156 * 2) + (31 * 3) = 781 + 312 + 93 = 1186 으로 정답과 3 차이가 납니다.
지금까지 계산한 것은 A <-> E 의 차이라는 것을 놓친 것입니다.
그래서 시작값인 A(1), EA(1), EIA(1) 의 3가지 경우를 추가하면, 정답과 일치하게 됩니다.
(이 값은 결국 word 의 길이가 되겠더라구요!)
저는 그래서 코딩할 때 각 경우를 vertical, horizontal 값을 계산하는 것이라고 생각하고
아래와 같은 코드를 도출하였습니다.
answer = getHorizonLen(word) + getVerticalLen(word)
3. 해결 코드
function solution(word) { var answer = getHorizonLen(word) + getVerticalLen(word); return answer; } function getVerticalLen(word) { const wordList = ['A', 'E', 'I', 'O', 'U']; let result = 0; word.split('').forEach((item, idx) => { const wordIdx = +wordList.indexOf(item); const multiplyVal = [781, 156, 31, 6, 1]; result += wordIdx * multiplyVal[idx]; }); return result; } function getHorizonLen(word) { return word.length; }
4. 문제해결 능력 UP! 되짚어보기
같은 알고리즘인데, 한 줄 풀이
function solution(words) { return words.split('').reduce((r, c, i) => r + [781, 156, 31, 6, 1][i] * ['A', 'E', 'I', 'O', 'U'].indexOf(c) + 1, 0); }
DFS
function solution(word) { function dfs(p) { if (p.length > 5) return; answer[p] = cnt; cnt++; for (let w of "AEIOU") { dfs(p + w); } } const answer = {}; let cnt = 0; dfs(""); return answer[word]; }
5. References
from http://dongurami0502.tistory.com/28 by ccl(A) rewrite - 2021-11-06 22:01:20