[프로그래머스] Swift - 모음사전 (LV.2)

👆문제풀러 가기👆

문제 설명

사전에 알파벳 모음 '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

 

 

 

풀이 [ 메모리: 16.5mb, 최대시간:  0.03ms ] 

func solution(_ word:String) -> Int {
    var word = word.map { String($0) }
    var dict = ["A": 1, "E": 2, "I": 3, "O": 4, "U": 5]
    var nums = [781, 156, 31, 6, 1]
    var sum = 0

    for i in 0..<word.count {
        if let n = dict[word[i]] {
            sum += nums[i] * (n-1) + 1
        }
    }

    return sum
}

문제를 받고 생각한 것.

1. word의 뒷 문자가 AEIOU 순서를 지나면 이전 문자가 다음문자로 넘어간다. 이를 이용한 규칙문제이다.
2. AEIOU가 1, 2, 3, 4, 5 순서라고 했을 때, AAAAA, AAAAE, AAAAI, AAAAO, AAAAU는 1 1 1 1 1 ... 1 1 1 1 5의 합이 순서가 된다.
3. AAAA = 4, AAAE= 10으로 6의 차이 발생, AAAI, AAAO, AAAU도 6의 배수만큼 증가한다.
4. 이 때 숫자로 표현하면 AAAA는 1 1 1 1, AAAE는 1 1 1 7이 된다. 즉, 1 + 6(n - 1)의 값의 등차수열이 된다.
5. AAA일 때는 1 1 1,  AAE는 1 1 32로 1 + 31(n-1)이 되며,
6. AAAAA와 AAAA 사이에는 5n + 1만큼의 등비수열이 형성된다.
7. 이를 반복하면 781, 156, 31, 6, 1이라는 배열을 생성할 수 있다.
8. 하지만 숫자가 단순히 5개 뿐이기에 하드코딩이 가능했을 뿐, 조금 더 범용성있는 코드를 위해 식으로 변환하면 아래와 같다.

 

func solution(_ word:String) -> Int {
    let word = word.map { String($0) }
    let dict = ["A": 1, "E": 2, "I": 3, "O": 4, "U": 5]
    var nums = [1]
    var sum = 0

    for _ in 1..<5 {
        if let num = nums.last {
            nums.append(num * 5 + 1)
        }
    }

    nums.reverse()

    for i in 0..<word.count {
        if let n = dict[word[i]] {
            sum += nums[i] * (n-1) + 1
        }
    }

    return sum
}

 

 

그런데 dfs로도 풀 수 있는 문제로 보인다.

AEIOU를 순서대로 배열에 넣어 모든 문자 조합을 생성하고, 해당 배열의 index를 찾으면 된다면, dfs로도 충분히 풀 수 있다.

하지만 위의 풀이와 달리 완전탐색이기 때문에 시간복잡도에서 손해를 볼 수 밖에 없다.

다른 풀이 [ 메모리: 16.5mb, 최대시간:  1.49ms ] 

func solution(_ word:String) -> Int {
    let alpha = "AEIOU".map { String($0) }
    var result = [String]()

    func dfs(_ str: String) {
        result.append(str)

        if str.count == 5 { return }

        for i in 0..<5 {
            dfs(str + alpha[i])
        }
    }

    dfs("")
    return result.firstIndex(of: word)!
}