swift permutation 구현

PS를 하는데 있어서 permutation을 사용할 일이 있어서 한번 짚고 넘어가려 한다. 내가 필요하다고 생각했던 문제는 2020 카카오 인턴 코딩테스트 문제에서 수식최대화 문제였다. 이 문제에서는 + - * 세가지의 연산자가 있을때 이 연산자들의 우선순위를 정해주어야 하는데 완전 탐색으로 모든 경우에 대해서 확인을 해봐야 했기 때문이다 즉 + - * 일 수도 있고 - + * 일수도 있다 즉 3! 6가지의 경우를 다 검사를 해봐야 했기 때문의 순열로 가능한 경우의 수를 다 구해야 했었기 때문에 순열을 사용하려고 생각 했다.

 

내가 참조 한 글은 하단의 글이다. 여기서 작성 해준 코드를 약간 변형해서 사용 했다.

https://github.com/raywenderlich/swift-algorithm-club/tree/2fdd8b8be1b3fcd17ad0394053e672f2bd1d3076/Combinatorics

raywenderlich/swift-algorithm-club

func permuteWirth<T>(_ a: [T], _ n: Int) -> [[T]] {
    if n == 0 {
        return [a]
    }
    var a = a
    var ret = permuteWirth(a, n - 1)
    for i in 0..<n {
        a.swapAt(i, n)
        ret += permuteWirth(a, n - 1)
        a.swapAt(i, n)
    }
    return ret
}

 

우리는 print 하기 보다는 return 값이 필요 하기 떄문에 n == 0 일때 반환하고 ret 배열에 합쳐서 반환하도록 하여 모든 경우를 탐색 가능하게 했다. 이 알고리즘의 원리는 모든 쌍을 한번씩 swap을 하는 알고리즘 이다. 참 이 순열을 실행할때 3개의 원소라면 n의 값을 3을 주는 것이 아니라 하나 뺀 2를 주어야 한다.