[알고리즘 - Swift] 순열과 조합 구현하기

순열과 조합

코테 문제를 풀다보면 순열과 조합이 필요한 경우가 있다. Swift에서는 순열과 조합을 직접 구현해야 한다.

순열과 조합은 각각 Stack, 재귀를 통해 구현할 수 있다. 어떻게 구현하는지 순열부터 알아보자.

---

순열

순열은 서로 다른 m개에서 n개를 골라 줄세우는 것이다. (mPn)

줄을 세우기 때문에 요소들의 순서 또한 경우의 수에 영향을 준다.

 

Stack

func permutation<T: Comparable>(_ array: [T], _ num: Int) -> [[T]] {
    var result = [[T]]()
		
		/// 주어진 원소 개수보다 많은 가짓수를 뽑을 수 없음
    guard num <= array.count else { return result }
    
		/// 튜플 형태로 stack에 삽입. (방문 히스토리, 방문 유무)
    var stack: [([T], [Bool])] = array.enumerated().map {
        var visited = Array(repeating: false, count: array.count)
        visited[$0.offset] = true

        return ([$0.element], visited)
    }

    while stack.count > 0 {
        let current = stack.removeLast()
        
        let elements = current.0
        var visited = current.1
        
				/// 주어진 가짓수만큼 다 뽑았으면 result에 추가하고 다음 반복으로 넘어가기
        if elements.count == num {
            result.append(elements)
            continue
        }

				/// 방문 유무를 보면서 아직 방문 안 한 곳 stack에 추가하기
        for i in 0..<array.count {
            if visited[i] == true { continue }
            
            visited[i] = true
            stack.append((elements + [array[i]], visited))
            visited[i] = false
        }
    }

    return result
}

 

재귀

func permutation<T: Comparable>(_ array: [T], _ num: Int) -> [[T]] {
    var result = [[T]]()
    
		/// 주어진 원소 개수보다 많은 가짓수를 뽑을 수 없음
    guard num <= array.count else { return result }
    
		/// 방문 표시 할 배열 
    var visited = Array(repeating: false, count: array.count)
    
    func cycle(_ current: [T]) {
				/// 주어진 가짓수만큼 다 뽑았으면 result에 추가하고 다음 반복으로 넘어가기
        if current.count == num {
            result.append(current)
            return
        }

        for i in 0..<array.count {
						/// 방문했다면 다음 반복으로 넘어가기
            if visited[i] { continue }
            else {
								/// 방문하지 않았다면, 방문표시 한 것을 넘겨주고, 방문 히스토리에도 추가하고 더 파고들기
                visited[i] = true
                cycle(current + [array[i]])
                visited[i] = false
            }
        }
    }

    cycle([])
    
    return result
}

 

 

조합

조합은 서로 다른 m개에서 n개의 조합을 찾는 것이다. (mCn)

순열과 달리 줄을 세울 필요가 없어서 순서와 상관 없이 구성만 따지면 된다.

 

Stack

func combination<T: Comparable>(_ array: [T], _ num: Int) -> [[T]] {
    var result = [[T]]()
    
		/// 주어진 원소 개수보다 많은 가짓수를 뽑을 수 없음
    guard num <= array.count else { return result }
    
		/// 튜플 형태로 stack에 삽입. (방문 히스토리, 현재 위치)
    var stack = array.enumerated().map { ([$0.element], $0.offset) }
    
    while stack.count > 0 {
        let current = stack.removeLast()
        
        let elements = current.0
        var index = current.1
        
				/// 주어진 가짓수만큼 다 뽑았으면 result에 추가하고 다음 반복으로 넘어가기
        if elements.count == num {
            result.append(elements)
            continue
        }
        
				/// 현재 위치가 끝이라면 다음 반복으로 지나가기
				/// 다음에 방문할 곳은 +1로 표시. 이렇게 함으로써 일종의 방향을 가짐. 방향을 가짐으로써 중복 방문을 면함. 
        guard (index+1) < array.count else { continue }
        
				/// 다음에 방문할 곳 stack에 추가
        for i in (index+1)..<array.count {
            stack.append((elements + [array[i]], i))
        }
    }
    
    return result
}

 

재귀

func combination<T: Comparable>(_ array: [T], _ num: Int) -> [[T]] {
    var result = [[T]]()

    /// 주어진 원소 개수보다 많은 가짓수를 뽑을 수 없음
    guard num <= array.count else { return result }
    
    func cycle(_ index: Int, _ current: [T]) {
				/// 주어진 가짓수만큼 다 뽑았으면 result에 추가하고 다음 반복으로 넘어가기
        if current.count == num {
            result.append(current)
            return
        }
        
				/// index부터 범위를 시작하면서 일종의 방향성을 갖게 함
        for i in index..<array.count {
						/// 다음 index를 지정해주고, 방문 히스토리에도 추가해줘서 한 번 더 파고듦
            cycle(i+1, current + [array[i]])
        }
    }
    
    cycle(0, [])
    
    return result
}

 

 

활용 문제

프로그래머스 - 메뉴 리뉴얼 (lv2)

프로그래머스

 

sol) 조합 (DFS)

/1

주어진 course에 대해

각 orders에서 

course의 수에 맞는 조합 구하고

 

/2

주어진 course에 대해

course의 수를 충족하는 조합 중에서 가장 많이 반복된 것 찾기

 

import Foundation

fileprivate func solution(_ orders:[String], _ course:[Int]) -> [String] {
    var ans = [String]()
    let arr = orders.map{ Array($0).map { String($0) } }
    var dict = [Int:[[String]]]()
    
    for n in course {
        var values = [[String]]()
        for str in arr {
            values += combination(str, n)
        }
        dict[n] = values
    }
    
    for n in course {
        let values = dict[n]!.map { $0.joined() }
        var check = [String:Int]()
        
        for i in Set(values) {
            check[i] = values.filter{ $0 == i }.count
        }
        
        let max = check.values.max()
        
        for i in check {
            if i.value > 1 && i.value == max {
                ans.append(i.key)
            }
        }
    }
    
    return ans.sorted()
}

func combination<T: Comparable>(_ array: [T], _ num: Int) -> [[T]] {
    var result = [[T]]()
    
    guard num <= array.count else { return result }
    
    func cycle(_ index: Int, _ current: [T]) {
        if current.count == num {
            result.append(current.sorted())
            return
        }
        
        for i in index..<array.count {
            cycle(i+1, current+[array[i]])
        }
    }
    
    cycle(0, [])
    
    return result
}