Swift - 순열과 조합 구현하기

Swift - 순열과 조합 구현하기

 

 

 순열과 조합을 왜 직접 구현하나요..?

 

스위프트에는 순열과 조합을 라이브러리 형태로 제공하는 것이 없다. 

때문에 코딩테스트에서 사용할 때 직접 구현해서 사용해야 한다...ㅎ

 

전체적인 맥락을 이해하면 쉽기 때문에 정리해서 필요할때마다 사용하고자 정리한다

 

 순열

 

순열은 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열이라고 한다. 

핵심은 순서가 존재하기 때문에 [1, 2, 3, 4]에서 [1, 2]와 [2, 1]을 구분해서 카운트하는 것이 핵심이다.

 

func permutation(_ target: [String], _ targetNum: Int) {
	// 순열이 되는 수의 조합을 담는 곳
    var results: [[String]] = []
    // 현재 탐색하고 있는지 확인하는 배열
    var check = [Bool](repeating: false, count: target.count)
    
    func permute(_ arr: [String]) {
    	// 순열의 개수가 뽑으려는 숫자와 같을 때 종료
        if arr.count == targetNum {
            results.append(arr)
            return 
        }
        for i in 0..<target.count {
        	// 현재 탐색하는 인덱스가 배열에 담겨있다면 넘어간다.
            if check[i] == true {
                continue
            } else {
                check[i] = true
                permute(arr + [target[i]])
                check[i] = false
            }
        }
    }
    permute([])
}

재귀를 이용하니 꼭 DFS와 비슷해 보인다..

 

 조합

 

조합은 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관없이 선택하는 혹은 나열하는 것을 조합이라고 한다.

핵심은 순서와 상관이 없기 때문에 check배열을 사용하지 않고 앞으로만 탐색하는 것이다. 

 

인덱스 0부터 탐색한다면 인덱스가 1일때 0일때의 값을 넣고 1부터 다시 for문을 도는 형식이다.

예시로 [1, 2, 3, 4]가 있을 때 순열의 경우는 [1, 2], [1, 3], [1, 4]를 돌고 [2, 1]을 돌게 되는데 이는 index를 앞에서부터 또 돌기 때문이다. 조합은 [1, 2], [1, 3], [1, 4]에서 [2, 1]이 아닌 [2, 3]으로 가야 관계없이 경우의 수를 카운트 할 수 있다.

 

Int나 String에 제한되지 않은 범용적인 것을 담기 위해 T를 사용해서 구현했다! (다른 분의 코드를 참고)

 

func combination<T: Comparable>(_ targetArr: [T], _ n: Int) -> [[T]] {
    var results = [[T]]()
    if targetArr.count < n { return results }
    
    func cycle(_ idx: Int, _ arr: [T]) {
        if arr.count == n {
            results.append(arr)
            return
        }
        for i in idx..<targetArr.count {
            cycle(i + 1, arr + [targetArr[i]])
        }
    }
    cycle(0, [])
    
    return results
}