문제 설명
사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.
단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- word의 길이는 1 이상 5 이하입니다.
- word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.
입출력 예
word | result |
"AAAAE" | 6 |
"AAAE" | 10 |
"I" | 1563 |
"EIO" | 1189 |
입출력 예 설명
입출력 예 #1
사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. "AAAAE"는 사전에서 6번째 단어입니다.
입출력 예 #2
"AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다.
입출력 예 #3
"I"는 1563번째 단어입니다.
입출력 예 #4
"EIO"는 1189번째 단어입니다.
풀이
입출력 예제 중 3번째인 I는 (첫 단어가 A로 나올 수 있는 경우의 수 + 첫 단어가 E로 나올 수 있는 경우의 수 + 1) 인것을 알 수 있습니다. 따라서 첫 단어 하나로 나올 수 있는 경우의 수는 781입니다.
fun solution(word: String): Int {
// 한 단어로 만들 수 있는 경우의 수
var swc = when(word[0]){
'A' -> 1
'E' -> 781 + 1
'I' -> 781 * 2 + 1
'O' -> 781 * 3 + 1
'U' -> 781 * 4 + 1
else -> 0
}
return ted("", word.substring(1)) + swc
}
var count = 0
var res = 0
fun ted(word: String, compareWord: String): Int{
val alpa = arrayListOf("A", "E", "I", "O", "U")
alpa.forEach{
if(word == compareWord) {
res = count
return count
}
if(word.length == 4)
return@forEach
count++
ted(word+it, compareWord)
}
return res
}
간단합니다. 첫 단어로 재귀 범위를 줄이고 그 다음 단어부터 재귀반복하는 형태입니다.
다른 사람의 풀이
이를 수학적으로 접근하면 사전에 알파벳 모음 "A", "E", "I", "O", "U"만을 사용하여 만들수 있는 길이 5 이하의 단어들이 수록되있습니다. 첫 단어는 "A", 두 번째 단어는 "AA", 마지막 단어는 "UUUUU"입니다.
위 조건으로 경우의 수를 계산하면
문자의 종류는 5개, 문자열의 길이는 1, 2, 3, 4, 5 개
문자열의 길이별 경우의 수 의 총 합 = 5^1 + 5^2 + 5^3 + 5^4 + 5^5 = 5 + 25 + 125 + 625 + 3125 = 3905입니다.
문자간의 거리 = 경우의 수 총 합 / 문자열 길이의 경우의 수(1=5, 2= 25, 3= 125, 4=625, 5=3125)입니다.
따라서
- 첫 번째 자리 경우 간격 781 (3905 / 5) ex) AXXXX -> EXXXX
- 두 번째 자리 경우 간격 156 (3905 / 25) ex) AAXXX -> AEXXX
- 세 번째 자리 경우 간격 31 (3905 / 125) ex) AAAXX -> AAEXX
- 네 번째 자리 경우 간격 6 (3905 / 625) ex) AAAAX -> AAAEX
- 다섯 번째 자리 간격 1 (3905 / 3125) ex) AAAAA -> AAAAE
예시로 AAAE를 들어보면
A는 첫 번째 자리로 간격은 781, 순서로 0번째 : 781 * 0 + 1
A는 두 번째 자리로 간격은 156, 순서로 0번째 : 156 * 0 + 1
A는 세 번째 자리로 간격은 156, 순서로 0번째 : 31 * 0 + 1
E는 네 번째 자리로 간격은 6 순서로 1번째니까 6 * 1 + 1
곱한 값은 첫 번째 단어 A로 부터의 간격이기 때문에 그 다음 값을 구해야 하므로 1을 더했습니다.
정답 : 1 + 1 + 1 + 6 + 1 = 10
class Solution {
public int solution(String word) {
int answer = 0;
// 종 문자열 길이
int length = word.length();
// 종류의 수
int numberOfWords = 5;
// 경우의 수 총합
int max = 0;
for(int i = 1; i <= numberOfWords; i++) {
max += Math.pow(numberOfWords, i);
}
// ['A', 'E', 'I', 'O', 'U'] 순서 [0, 1, 2, 3, 4]
for (int i = 1; i <= length; i++) {
if (word.charAt(i-1) == 'A') {
answer += 1;
} else if (word.charAt(i-1) == 'E') {
answer += ((max / Math.pow(numberOfWords, i)) * 1) + 1;
} else if (word.charAt(i-1) == 'I') {
answer += ((max / Math.pow(numberOfWords, i)) * 2) + 1;
} else if (word.charAt(i-1) == 'O') {
answer += ((max / Math.pow(numberOfWords, i)) * 3) + 1;
} else {
answer += ((max / Math.pow(numberOfWords, i)) * 4) + 1;
}
}
return answer;
}
}
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
달리기 경주 (0) | 2023.04.11 |
---|---|
롤케이크 자르기(Lv.2) (0) | 2022.10.28 |
피로도(Lv.2) (0) | 2022.10.12 |
오픈채팅방(Lv.2) (0) | 2022.10.11 |
프린터(Lv.2) (0) | 2022.10.10 |