Swift 알고리즘 (2)
[실수 다루기]
제곱, 제곱근
import Foundation
let x: Int = 5
let sqrtX = sqrt(Double(x)) // 제곱근
let powX = pow(Double(x)) // 제곱
print(Int(sqrtX)) // 2
print(powX) // 25.0
Swift
복사
분수
Int a, Int b의 나눗셈 연산을 해서 Double형 결과를 얻고 싶다면, 반드시 a와 b 모두 Double로 형 변환을 시켜주며 나눗셈 해야한다.
let a: Int = 1
let b: Int = 2
print(a / b) // 0
print(Double(a / b)) // 0.0
print(Double(a) / Double(b)) // 0.5
Swift
복사
[정렬]
조건 정렬
import Foundation
let arr = [3, 1, 2, 5, 4]
let arr2 = arr.sorted(by: >) // 내림차순
let arr3 = arr.sorted() // 오름차순
struct Student {
let name: String
let age: Int
}
let studentArray = [Student(name: "Kim", age: 28), Student(name: "HJ", age: 28), Student(name: "YJ", age: 23)]
// 나이 오름차순 정렬
let sortedStudentArray = studentArray.sorted(by: { $0.age < $1.age })
Swift
복사
다중 조건 정렬
튜플의 특성을 이용해서 다중 정렬을 할 수 있다.
•
(”a”, “1”) < (”b”, “1”) : 첫 번째 원소부터 비교, a < b 이므로 두 번째 원소는 관심 X
•
(”a”, “1”) < (”a”, “2”) : 첫 번째 원소 비교했으나 같으면 두 번째 원소로 판단
let arr = [["a", "2"], ["a", "1"], ["b", "1"], ["b", "3"], ["b", "2"], ["c", "4"]]
print(arr.sorted(by: { ($0[0], $0[1]) < ($1[0], $1[1]) }))
// [["a", "1"], ["a", "2"], ["b", "1"], ["b", "2"], ["b", "3"], ["c", "4"]]
print(arr.sorted { $0[0] == $1[0] ? $0[1] > $1[1] : $0[0] < $1[0] })
// [["a", "2"], ["a", "1"], ["b", "3"], ["b", "2"], ["b", "1"], ["c", "4"]]
Swift
복사
[반복문 응용]
stride
for i in stride(from: 0, to: 7, by: 2) {
print(i)
}
// 0, 2, 4, 6
Swift
복사
[고차함수]
map, filter, reduce
// 기본 배열
let arr = [1, 2, 3, 4, 5, 6, 7, 8]
// <filter>
// 짝수만 걸러내기
let evenFilter = arr.filter { (num) -> Bool in return num % 2 == 0 }
print(evenFilter) // [2, 4, 6, 8]
let evenFilter2 = arr.filter { $0 % 2 == 0 }
print(evenFilter2) // [2, 4, 6, 8]
// <map>
// 문자열 타입으로 바꾸기
let toString = arr.map{ (num: Int) -> String in
return "\(num)"
}
print(toString) // ["1", "2", "3", "4", "5", "6", "7", "8"]\n
let toString2 = arr.map { "\($0)" }
print(toString2) //[ "1", "2", "3", "4", "5", "6", "7", "8"]\n
// <reduce>
// 모든 원소를 문자열에 담아 압축하기
let arrStr = arr.reduce ("") { (first, second) -> String in
return "\(first)\(second)"
}
print(arrStr) // "12345678\n"
let arrStr2 = arr.reduce("") { "\($0)\($1)" }
print(arrStr2) // "12345678\n"
Swift
복사
[순열과 조합]
Combinations (조합)
Python에서는 itertools에서 combinations를 제공해주지만 Swift에서는 제공해주지 않는다.
import Foundation
// combination 함수는 제네릭 타입 'T'를 가지며, '[T]' 타입의 배열을 입력으로 받고 'k'라는 정수
// 를 받는다. 반환값은 '[[T]]', 즉, 요소가 'T' 타입의 배열들의 배열
func combination<T>(_ elements: [T], _ k: Int) -> [[T]] {
var result = [[T]]()
func combi(_ index: Int, _ now: [T]) {
if now.count == k {
result.append(now)
return
}
for i in index..<elements.count {
combi(i + 1, now + [elements[i]])
}
}
combi(0, [])
return result
}
let arr = [1, 2, 3, 4]
let combi = combination(arr, 3)
print(combi) // [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
Swift
복사
Permutations (순열)
func permutation<T>(_ elements: [T], _ k: Int) -> [[T]] {
// 생성된 모든 가능한 순열이 저장된다
var result = [[T]]()
// 각 요소가 이전에 방문한 적이 있는지를 표시한다
var visited = [Bool](repeating: false, count: elements.count)
// 재귀적 내부 함수(클로저)
// 현재까지 만들어진 순열을 나타내는 now 배열을 매개변수로 받는다
func permut(_ now: [T]) {
if now.count == k {
result.append(now)
return
}
for i in 0..<elements.count {
if visited[i] == true { continue }
visited[i] = true
permut(now + [elements[i]])
visited[i] = false
}
}
permut([])
return result
}
let arr = [1, 2, 3, 4]
let permu = permutation(arr, 3)
print(permu) // [[1, 2, 3], [1, 2, 4], [1, 3, 2], [1, 3, 4], [1, 4, 2], [1, 4, 3], [2, 1, 3], [2, 1, 4], [2, 3, 1], [2, 3, 4], [2, 4, 1], [2, 4, 3], [3, 1, 2], [3, 1, 4], [3, 2, 1], [3, 2, 4], [3, 4, 1], [3, 4, 2], [4, 1, 2], [4, 1, 3], [4, 2, 1], [4, 2, 3], [4, 3, 1], [4, 3, 2]]\
Swift
복사
[기타]
dropLast, popLast, removeLast
보통 Array를 스택으로서 하용할 때 활용
•
dropLast(n) : Array를 변경하지는 않고, 마지막 n개를 제외한 원소들을 반환
•
popLast() : Array의 마지막 원소를 제거해버리고, 남은 원소들 반환, 원소가 비어있을 시 nil 반환
•
removeLast(n) : Array의 마지막 원소 n개를 제거해버리고, 남은 원소들을 반환, 원소가 비어있을 시 컴파일 에러
import Foundation
// 시간 측정 메서드
public func progressTime(_ closure: () -> ()) -> TimeInterval {
let start = CFAbsoluteTimeGetCurrent()
closure()
let diff = CFAbsoluteTimeGetCurrent() - start
return (diff)
}
// 긴 배열
var arr = [Int](repeating: 0, count: Int(pow(10.0, 6)))
// arr의 마지막 4개의 원소를 pop한 배열의 결과를 얻고 싶다
// 1. dropLast 한 것을 대입 -> 0.35초
progressTime {
let arr2 = arr.dropLast(4)
}
// 2. index 슬라이싱 대입 -> 0.32초
progressTime {
let arr2 = arr[arr.startIndex..<arr.index(arr.startIndex, offsetBy: arr.endIndex - 4)]
}
// 3. popLast() 4번 -> 0.0002초
progressTime {
arr.popLast()
arr.popLast()
arr.popLast()
arr.popLast()
}
// 4. removeLast(4) -> 0.0007초
progressTime {
arr.removeLast(4)
}
Swift
복사
결론
•
popLast() 또는 removeLast() 가 훨씬 빠르다
•
popLast() 쓰자
split vs components
문자열을 분리하는 split과 components의 차이점
•
성능은 split가 더 빠르기 때문에 웬만하면 split 쓰기
import Foundation
var str = "a b c d e"
var str2 = "a b c d e"
print(str.split(separator: " "))
// ["a", "b", "c", "d", "e"]
print(str.components(separatedBy: " "))
// ["a", "b", "c", "d", "e", ""]
print(str2.split(separator: " "))
// ["a", "b", "c", "d", "e"]
print(str2.components(separatedBy: " "))
// ["a", "", "b", "", "c", "", "d", "", "e"]
Swift
복사
백준 풀 때 입력 빨리받기
•
백준에서 이걸 쓰면 시간초가 안나는 경우가 상당히 많다.
•
파이썬의 sys.stdin.readline() 역할이라고 생각하면 된다.
•
File 입력이라 Xcode 콘솔 상에서 테스트하긴 힘들다
import Foundation
final class FileIO {
private let buffer:[UInt8]
private var index: Int = 0
init(fileHandle: FileHandle = FileHandle.standardInput) {
buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
}
@inline(__always) private func read() -> UInt8 {
defer { index += 1 }
return buffer[index]
}
@inline(__always) func readInt() -> Int {
var sum = 0
var now = read()
var isPositive = true
while now == 10
|| now == 32 { now = read() } // 공백과 줄바꿈 무시
if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
while now >= 48, now <= 57 {
sum = sum * 10 + Int(now-48)
now = read()
}
return sum * (isPositive ? 1:-1)
}
@inline(__always) func readString() -> String {
var now = read()
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
let beginIndex = index-1
while now != 10,
now != 32,
now != 0 { now = read() }
return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
}
@inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
var now = read()
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
let beginIndex = index-1
while now != 10,
now != 32,
now != 0 { now = read() }
return Array(buffer[beginIndex..<(index-1)])
}
}
/* Usage
// stdin Input: 1
import Foundation
let fIO = FileIO()
let n = fIO.readInt()
print(n) // 1
/*
Swift
복사
[기억해둘 것]
1.
Set에는 튜플이 들어갈 수 없다
a.
Set<(Int, Int)> 는 불가능하다
2.
split(separator: “ “) 대신 split{$0 == “ ”} 을 쓰자
var str = "1 2 3"
let arr = str.split(separator: " ").map{ Int(String($0))! }
let arr2 = str.split{ $0 == " " }.map{Int(String($0))! }
Swift
복사
Reference
