[프로그래머스] 모음사전 (수학)

문제 소개

이전 푼 모음 사전 - 프로그래머스 문제 다른 방식으로도 정리합니다. 참고
이 문제는 모음만을 사용해 만들 수 있는 단어들 중에서, 주어진 단어가 사전에서 몇 번째인지 구하는 문제입니다.
사전은 "A"부터 "UUUUU"까지의 모든 조합이 포함되며, 사전순으로 정렬되어 있다고 가정합니다.

문제 링크: 모음 사전 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 단어 길이는 최대 5자리, 사용할 수 있는 문자는 총 5개 → 가능한 단어 수는 유한
2. 각 자리마다 A~U 중 어떤 문자가 오는지에 따라 앞에 몇 개 단어가 오는지 계산 가능
   첫 글자가 'A'일 때
   'A'로 시작하는 모든 단어를 생각해보면 다음과 같은 구조:
   • A (1글자) = 1개
   • AA, AE, AI, AO, AU (2글자) = 5개
   • AAA ~ AUU (3글자) = 5 × 5 = 25개
   • AAAA ~ AUUU (4글자) = 5 × 5 × 5 = 125개
   • AAAAA ~ AUUUU (5글자) = 5⁴ = 625개
     📌 총합 = 1 + 5 + 25 + 125 + 625 = 781개
     즉, 'A'로 시작하는 단어 블록의 크기는 781
     → 첫 글자가 'E'면 앞에 'A'로 시작하는 781개의 단어가 앞서 있다는 뜻
3. 즉 각 자릿수마다 자리별 이전 경우의 수를 곱해 계산 가능

---

해결 과정 및 코드

핵심 아이디어

1. 각 자릿수마다 앞에 오는 알파벳 개수를 계산하기 위해 고정된 가중치(per)를 활용
2. "AEIOU"에서 해당 문자의 인덱스를 구해, 가중치와 곱한 값을 누적
3. 단어마다 자기 자신도 포함되므로 마지막에 +1을 추가

코드

시간 복잡도 : O(N)

class Solution {
    public int solution(String word) {
        int answer = 0, per = 3905;

        // 자리별 가중치: [781, 156, 31, 6, 1]
        // 자리별 가중치 계산용 (자릿수가 올라갈수록 1/5씩 줄어듦으로 per /= 5)
        // 3905 = 5^5 + 5^4 + 5^3 + 5^2 + 5^1
        for (String s : word.split("")) {
            answer += "AEIOU".indexOf(s) * (per /= 5) + 1; // 자기 자신 포함 +1
        }

        return answer;
    }
}