순열(Permutation)

순열

  서로 다른 n개의 숫자 중, r개의 숫자를 선택하여 만들 수 있는 배열들

 

e.g.  [1, 2, 3]이라는 배열의 숫자 중, 2가지 숫자를 골라서 만든 순열을 나열한다면 아래와 같을 것이다.

array = [1, 2, 3]

permutation = [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]

 

 

 잘 돌아보면 순열에는 규칙이 있다. 

  1. 한번 선택한 숫자는 다시 선택할 수 없다.

  2. 그러므로 다음 숫자에선 '이미 선택한 숫자를 제외한' 숫자들 중 하나를 선택할 수 있게 된다. (하단 참고)

array = [1, 2, 3]

[1, 2] - 이미 1을 선택 했으므로, 남은 숫자는 2, 3
[1, 3]

[2, 1] - 이미 2을 선택 했으므로, 남은 숫자는 1, 3 
[2, 3]

[3, 1] - 이미 3을 선택 했으므로, 남은 숫자는 1, 2 
[3, 2]

 

 

  그렇다면, 2개의 숫자를 고르는 방법을 코드로 만들자면?

솔직히 필자는 for loop문을 중첩한 것이 가장 먼저 떠올랐다....

func forLoopPermutation(array: [Int]) {
	let resultArray = [[Int]]()
    
	for (index1, value1) in array {
    	for (index2, value2) in array {
        	// 같은 index가 아니라면 결과 배열에 추가하기
        	if index1 != index2 {
            	let newValue = [value1, value2]
                resultArray.append(newValue)
            }
        }
    }
}

이렇게...! (심지어 이렇게 해서 하단의 문제도 한개 풀음... 사실 2개 풀었는데 하나는 시간초과나고 하나만 통과..)

[Implementation] Divisible Sum Pairs

 

 

하지만 들어가는 배열의 길이도 모를 뿐더러, 만약 뽑아야 하는 숫자가 2개가 아니라 5개라면 for loop문을 5번이나 중첩..?? 

그럼 시간복잡도가 미친듯이 가중되기에.... 상당히 비추한다ㅠㅠ

 

 

 

  그렇다면, 어떻게 구하면 될까?

// array의 숫자를 targetNum만큼 뽑아서 만들 수 있는 순열의 갯수를 리턴하는 함수
func permutationCount(_ array: [Int], _ targetNum: Int) -> Int {
    // 결과로 나온 배열들을 받을 배열
    var result = [[Int]]()
    // 이미 사용한 숫자인지 체크하기 위한 bool 타입 배열, default값은 false로 세팅
    var visited = [Bool](repeating: false, count: array.count)
    
    // 재귀함수로 사용할 것이므로, 초기값 받을 파라미터 생성
    func permutation(_ nowPermute: [Int]) {
        // 지정한 뽑을 갯수만큼 배열이 담긴 경우, result에 append하기
        if nowPermute.count == targetNum {
            result.append(nowPermute)
            return
        }
        //
        for i in 0..<array.count {
            // 해당 index의 숫자 사용 여부 체크 (방문한 경우 다음 주기로 넘기기)
            if visited[i] == true {
                continue
            }
            // 사용 안 한 숫자인 경우
            else {
                // 사용완료 처리
                visited[i] = true
                // 초기 배열 + [방문 안한 숫자의 값] 넣고 다시 함수 실행(재귀함수)
                permutation(nowPermute + [array[i]])
                // 다음 주기에는 다른 숫자를 사용하기에 뽑을 수 있도록 false로 세팅
                visited[i] = false
            }
        }
    }
    permutation([])
    
    return result.count
}

(참고: https://icksw.tistory.com/180)

이렇게 재귀함수를 활용하여 풀 수 있는 방법이 있다.

해당 index의 사용 여부를 체크해서, 이미 사용한 요소는 다시 선택할 수 없도록 구현할 수 있다.