[Swift] [65일차] 1641_LEET 조합

1641. Count Sorted Vowel Strings

---

문제설명

1. 모음으로 문자열 조합할 것.
2. 주어진 N길이만큼의 조합을 만들것
3. 순서를 지켜라 (e다음에는 a가 나올 수 없음)

---

문제 풀이

1. 이거 또 dfs로 풀어야하나? 고민하다가 결국 이거 중복X 조합으로 풀리는거 아닌가 싶어서 그쪽으로 방향을 틀었다.
2. 일단 N=3이라면 예시는 이렇게 35개가 될 것인데, 이게 결국

aaa, aae, aai, aao, aau, aee, aei, aeo, aeu, aii, aio, aiu, aoo, aou, auu, 
eee, eei, eeo, eeu, eii, eio, eiu, eoo, eou, euu, iii, iio, iiu, ioo, iou,
iuu, ooo, oou, ouu, uuu

7!/4!(3!) = 35 라서 알게됐다.

그래서 결론은 이거 C(재료개수+길이(n)-1,재료개수 -1))이라서 길이가 3이면 C(7,4)랑 같은것이다

---

그래서 일단 factorial 함수를 만들어줬다.

 func factorial(_ n: Int) -> Int {
        var answer = 1
        for i in 1 ... n {
            answer *= i
        }
        return answer
    }

1차 제출

class Solution {
    func factorial(_ n: Int) -> Int {
        var answer = 1
        for i in 1 ... n {
            answer *= i
        }
        return answer
    }

    func countVowelStrings(_ n: Int) -> Int {
        var answer = 5
        let a = 5 + n-1
        let b = 5-1
        let c = a-b

        answer = factorial(a) / (factorial(b) * factorial(c))
        return answer
    }
}

를 하려했으나 , 다음과 같이 숫자가 n=33으로 커지니까 overflow로 떴다. Int64를 초과하기 때문

이게 결국 k-1이 항상 4다보니까

C(n+4,4) = (n+4)*(n+3)....(n+1) / (4!) 로 하고, 그 나머지 (factorial(b) * factorial(c)) 이렇게하지말고 그냥 4!로 나눠주면서 C로 계산하지않고 미리 나눠준 형태로 해야할 것 같았다.

class Solution {
    func countVowelStrings(_ n: Int) -> Int {
        var answer = 1
        let a = n + 4
        let b = 4

        for i in 0 ..< b {
            answer *= (a - i) // (n+4에 해당 , 하나씩 줄어들을 것 )
            answer /= (i + 1)
        }

        return answer
    }
}

결국 factorial을 사장시키고 훨씬더 간결하게 중간에 나눠주는 형태로 수정을 했더니 에러에서는 벗어났고, 제출했더니 다행히..

타인의코드

class Solution {
    func countVowelStrings(_ n: Int) -> Int {
        var startingWith = [1, 1, 1, 1, 1]
        var sums = [1, 2, 3, 4, 5]

        for _ in 0 ..< n - 1 {

            startingWith[0] = sums[4]
            startingWith[1] = sums[4] - sums[0]
            startingWith[2] = sums[4] - sums[1]
            startingWith[3] = sums[4] - sums[2]
            startingWith[4] = sums[4] - sums[3]
            // print(startingWith)

            sums[0] = startingWith[0]
            for i in 1 ..< startingWith.count {
                sums[i] = sums[i - 1] + startingWith[i]
            }
        }
        return sums[4]
    }
}

이게 결국 이게 4번만 계산해도 된다는걸 파악하면은 이렇게 DP로 푸신분들도 보였다.있음을 봤다. n만큼 반복하면서 계속해서 sms에 쌓아나가는 것인데, 메모리 복잡도가 가장 좋은 코드임을 확인할 수 있었다.