Notice
Recent Posts
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- 시험에자주나오는것만
- ios면접
- Safari Inspector
- hackerrank
- RC
- iOS앱 디버깅
- 앱의생명주기
- algorithm
- 프로그래머스
- 반응형프레임워크
- 카카오맵클론
- Bubble Search
- IOS
- ReactorKit UnitTest
- 코딩테스트입문
- mrc
- Swift디자인패턴
- UIKit
- AutoLayout
- Swift코딩테스트
- HackersRank
- Di
- firestore
- firebase
- SWIFT
- TDD
- unittest
- ARC
- RxSwift
- alamofire
Archives
- Today
- Total
샘성의 iOS 개발 일지
순열(Permutation) 본문
728x90
순열
서로 다른 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개 풀었는데 하나는 시간초과나고 하나만 통과..)
하지만 들어가는 배열의 길이도 모를 뿐더러, 만약 뽑아야 하는 숫자가 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의 사용 여부를 체크해서, 이미 사용한 요소는 다시 선택할 수 없도록 구현할 수 있다.
728x90
'iOS > Swift' 카테고리의 다른 글
[Tuist] 모듈 생성 자동화 하기 (tuist scaffold, .stencil) (0) | 2024.06.18 |
---|---|
[알고리즘] 이진 탐색 (Binary Search) (0) | 2023.07.12 |
Firebase Remote Config로 앱 제어하기 (0) | 2023.07.06 |
Swift의 프로그래밍 패러다임 (0) | 2023.06.03 |
OpenWeather API로 도시별 날씨 불러오기 (0) | 2023.03.24 |