파이썬으로 알고리즘을 풀땐 라이브러리를 사용해 직접 구현하지 않아도 되었었지만, 야생의 swift에선 직접 구현해주어야 한다.
BOJ_2800_괄호제거를 풀다가 정리해본다.
서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 것
순서에 상관이 있다는 말은, 같은 배열이 반복될 수 없다는 것이다.
func permutation<T: Comparable>(_ target: [T], _ targetNum: Int) {
var result = [[T]]()
var check = [Bool](repeating: false, count: target.count)
func permute(_ arr: [T]) {
if arr.count == targetNum {
result.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([])
print(result)
}비어있는 배열(
result)의 count가 원하는 target Count가 될 때까지 인덱스를 증가시켜가며 재귀적으로 순열 함수(permute)를 호출한다. 이때, 각 원소가 이미 추가됐는지 확인하기 위해 체크해주는 변수(check)를 따로 선언해주어 check 변수의 해당하는 인덱스 값이 false일 경우에만 배열에 추가해준다.
예를 들어 (1,2,3) 3개의 원소 중 2개를 순열로 나열한다고 했을 때, target 배열은 [1,2,3]이 되고, targetNum은 2가 될 것이다.
permute 함수를 살펴보면, arr은 원소를 담을 배열로 재귀적으로 호출되므로 arr에 원하는 targetNum만큼의 원소가 추가될 것이다.
arr의 원소 개수가 targetNum과 같아지면 result에 추가해주고 함수를 종료한다.
아닐 경우에는 중복 확인을 위해 check 변수를 통해 판단 후 arr에 추가해준다.
순열을 통해 나올 수 있는 배열은 [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]이 될 것이다.
서로 다른 n개의 원소에서 r개를 순서에 상관없이 나열, 선택하는 것
즉, 전체에서 중복없이 순서를 고려하지 않고 r개를 배열하는 경우의 수이다.
func combination<T: Comparable>(_ targetArr: [T], _ targetNum: Int, _ index: Int, _ arr: [T]) {
if arr.count == targetNum {
print(arr)
return
}
for i in index..<targetArr.count {
combination(targetArr, targetNum, i+1, arr + [targetArr[i]])
}
}조합에선, 순서가 상관없으므로 앞의 인덱스를 다시 확인할 필요가 없다.
주어진 배열을 나타내는 targetArr, 순열 코드에서 보았던 것과 동일하게 원하는 개수를 나타내는 targetNum, 원소를 담을 배열인 arr는 순열과 동일하다.
위와 동일한 예시로 (1,2,3)의 원소 중 2개를 조합으로 선택할 경우 나올 수 있는 배열은 [1, 2], [1, 3], [2, 3]이 될 것이다.
이 때 만약 for문이 index가 아닌 0에서 시작할 경우, [2, 1]와 같이 이미 나온 배열과 동일한 배열이 나올 수 있으므로 이전의 인덱스를 확인하기 위해 추가적으로 index프로퍼티를 받게 되는 것이다.
식으로 풀어쓰면 간단해 보이지만 아직 문제에 적용하는건 쉽지 않다... 더 많이 연습해야겠다...