Algorithm / 모음사전

𝕮𝖗𝖔𝖎𝖘𝖘𝖆𝖓𝖙·2025년 7월 22일

algorithm swift 프로그래머스

알고리즘 코드카타

목록 보기

49/59

문제

프로그래머스 / 모음사전

1) 문제 풀이(DFS/BFS 활용)

✅ 접근 방식

모든 단어 생성: "A", "E", "I", "O", "U" 모음을 사용하여 길이가 1부터 5까지의 모든 단어를 생성한다.
사전 순 정렬: 생성된 단어들을 사전 순으로 정렬한다.
순서 찾기: 정렬된 리스트에서 주어진 word를 찾아 인덱스를 반환한다.

func solution(_ word: String) -> Int {
    let vowels: [Character] = ["A", "E", "I", "O", "U"]
    var dictionary: [String] = [] // 모든 단어를 저장할 배열

    // 재귀 함수로 모든 단어 생성
    func generateWords(currentWord: String) {
        // 단어의 길이가 1 이상 5 이하일 경우 사전에 추가
        if !currentWord.isEmpty {
            dictionary.append(currentWord)
        }
        
        // 단어의 길이가 5가 되면 더 이상 확장하지 않고 리턴
        if currentWord.count == 5 {
            return
        }
        
        // 각 모음을 현재 단어 뒤에 붙여 새로운 단어 생성
        for vowel in vowels {
            generateWords(currentWord: currentWord + String(vowel))
        }
    }

    // 빈 문자열부터 단어 생성 시작
    generateWords(currentWord: "")
    dictionary.sort()
    
    // 주어진 단어의 인덱스를 찾아 반환 (인덱스는 0부터 시작하므로 +1)
    if let index = dictionary.firstIndex(of: word) {
        return index + 1
    }
    
    return -1 
}

결과

완전 탐색의 장단점

장점: 이해하기 쉽고 구현이 비교적 간단. 모든 경우의 수를 직접 생성하므로 논리적인 오류를 줄일 수 있다.
단점: 단어의 총 개수가 많아지면 성능 문제가 발생할 수 있다.
(이 문제에서는 5^1 + 5^2 + 5^3 + 5^4 + 5^5 = 5 + 25 + 125 + 625 + 3125 = 3905개로 충분히 작아서 괜찮음)

2) 문제 풀이(수학적 규칙 활용)

✅ 접근 방식

각 자릿수에서 모음이 변경될 때마다 단어의 총 개수가 어떻게 증가하는지 파악한다.
예를 들어 A 다음 E로 바뀌려면 'A'로 시작하는 모든 길이의 단어를 건너뛰어야 한다.

규칙 찾기
모음은 "A", "E", "I", "O", "U" 순서로 인덱스 0, 1, 2, 3, 4를 가진다.
- 한 자리수만 있을 때:
  - A는 첫 번째
  - E는 A로 시작하는 모든 단어 + 1
  - I는 A로 시작하는 모든 단어 + E로 시작하는 모든 단어 + 1
- 각 자리별로 '한 칸' 이동했을 때 건너뛰는 단어의 수
  - 길이 1: 1(A)
  - 길이 2: 5(AA, AE, AI, AO, AU)
  - 길이 3: 5 * 5 = 25
  - 길이 4: 5 5 5 = 125
  - 길이 5: 5 5 5 * 5 = 625
  각 자릿수에서 모음 하나가 바뀌면 건너뛰는 단어의 수는 1 + 5 + 25 + 125 + 625가 된다.
  즉, 이 규칙을 거꾸로 생각하면 아래와 같다.
  - 첫 번째 자리가 바뀔 때(A -> E): 781개의 단어를 건너뜀
  - 두 번째 자리가 바뀔 때(AA -> AE): 156개의 단어를 건너뜀
  - 세 번째 자리가 바뀔 때(AAA -> AAE): 31개의 단어를 건너뜀
  - 네 번째 자리가 바뀔 때(AAAA -> AAAE): 6개의 단어를 건너뜀
  - 다섯 번째 자리가 바뀔 때(AAAAA -> AAAAE): 1개의 단어를 건너뜀
  이를 통해 '가중치' 배열을 미리 계산할 수 있다.
  weights = [781, 156, 31, 6, 1]

func solution(_ word: String) -> Int {
    let vowels: [Character] = ["A", "E", "I", "O", "U"]
    let weights = [781, 156, 31, 6, 1]

    var result = 0 
    
    for (index, char) in word.enumerated() {
        if let charIndex = vowels.firstIndex(of: char) {
            result += charIndex * weights[index]
        }
    }
    
    result += word.count 
    
    return result
}