Swift 알고리즘 팁

김상우·2023년 1월 4일

swift 코딩테스트

Swift로 알고리즘 문제를 풀 때 꿀팁들을 정리해봤다 🐝

요새 기업 코딩테스트는 본인의 직무에 맞는 언어로 보게 하는 곳이 많아지는 추세라, iOS 개발자라면 파이썬 말고 Swift로도 연습을 해두는게 중요한 것 같다.

Swift로 코테치는 iOS 개발자들 화이팅 👏🏻

[문자열]

접두사, 접미사

prefix, suffix, dropFirst, dropLast

let s = "abcdef"		
let s1 = s.prefix(3)		// "abc"
let s2 = s.suffix(3)		// "def"
let s3 = s.dropFirst(3)		// "def"
let s4 = s.dropLast(3)		// "abc"

// 범위를 넘어간다면 알아서 조절
let s5 = s.prefix(100)		// "abc"

이 메서드들은 Array 에도 똑같이 적용된다.

인덱스 접근

import Foundation

let s = "abcdef"
let x = s[s.index(s.startIndex, offsetBy: 3)]	// "d"
// x 의 타입은 String 이 아닌 Character

// 배열과 문자열의 인덱스 접근법 비교
let arr = [0, 1, 2, 3, 4]
let str = "abcde"

// 배열은 편하게 인덱스 접근 가능
let arr2 = arr[0..<3]

// 문자열은 편하게 인덱스 접근 불가능. String.Index 형으로 접근해야 함
let i = str.startIndex
let j = str.index(i, offsetBy: 3)
let str2 = str[i..<j]

print(arr2) // [0, 1, 2]
print(str2) // abc

슬라이싱

문자열 str = abcdef 가 있을때 abc 만 남기고 자르고 싶을 경우
파이썬에서는 str[0:3] 문자열 슬라이싱을 하면 되었지만 Swift 에서는 지원하지 않는다.

let s5 = s[s.startIndex ..< s.index(s.startIndex, offsetBy: 3)]
// "abc"
// Swift 의 Index 로 자른 결과는 String 이 아닌 SubString 타입.
var stringList = [String]()
stringList.append(String(s5))	// 타입 변환 필요

뒤집기

import Foundation

let s = "abcde"
print(String(s.reversed()))	// "edcba"

곱셈

import Foundation

let str = "abc"
print(String(repeating: str, count: 3))	// "abcabcabc"

교체

import Foundation

let str = "abcde"	
// "하이de"
let str2 = str.replacingOccurrences(of: "abc", with: "하이")

[배열]

first, last

first, last 라는 키워드를 제공한다. 비어있을 시 nil 을 반환한다.

let str = "abc"
let arr = [1, 2, 3]
let arr2 = [Int]()

str.last    // "c"
arr.last    // 3

str.first   // "a"
arr.first   // 1

arr2.first  // nil

정수 → 배열

map 의 결과는 Array 형태이기 때문에 다음과 같은 방법으로 정수 → 배열 변환을 할 수 있다.

import Foundation

var x: Int = 12345
var arr = String(x).map{ Int(String($0))! }

print(arr) //[1, 2, 3, 4, 5]

배열 초기화

여러가지 형태의 배열 초기화 방법

let N = 5
let a = [Int](repeating: 0, count: N)
let b = [Int](0..<N)
let c = [Int](0..<N).map{2*($0)}
let d = [Int](0..<N).filter{$0%2 == 0}

print(a)    //[0, 0, 0, 0, 0]
print(b)    //[0, 1, 2, 3, 4]
print(c)    //[0, 2, 4, 6, 8]
print(d)    //[0, 2, 4]

[딕셔너리]

원소 확인

원소가 있는지 없는지는 그냥 딕셔너리에 키 값으로 접근했을 때 nil 인지 아닌지로 판단한다.

var myDict = [String : Int]()

if let val = myDict['a'] {
  	print(val)
}
else {
  	print("없음")
}

원소 개수 확인

count 로 딕셔너리 원소 개수를 확인할 수 있다. 비어있는 경우는 count == 0 이 아닌 isEmpty 를 활용하는 것이 좋겠다.

let myDict = ["a" : 1, "b" : 2, "c" : 3]

print(myDict.count)

if !(myDict.isEmpty) {
    print("비어있지 않음")
}

원소 삭제

key-pair 를 삭제하고 싶다면 nil 을 대입해주면 된다.

let myDict = ["a" : 1, "b" : 2, "c" : 3]

myDict[a] = nil

defaultDict

딕셔너리에 없는 값을 조회할 경우 디폴트값을 설정할 수 있다.

let myDict = ["a" : 1, "b" : 2, "c" : 3]

print(myDict["d", default: -1])

딕셔너리 비교

딕셔너리끼리도 == 연산을 할 수 있다.

var a = [String : Int]()
var b = [String : Int]()

a["a"] = 1
a["b"] = 2

b["b"] = 2
b["a"] = 1

print(a == b)	// true

b["c"] = 3

print(a == b) 	// false

주의점

딕셔너리 결과는 항상 옵셔널이기 때문에 옵셔널 처리에 주의해야한다.

let myDict = ["a" : 1, "b" : 2, "c" : 3]

if let a = myDict["a"], a > 0 {
    print("양수")
}

[큐 Queue]

Swift에서는 Queue를 지원해주지 않는다.
Array에서 popLast()라는 메서드와 removeFirst()라는 메서드가 있기는하다.

하지만 공식문서를 읽어보면 removeFirst()의 시간복잡도는 O(N)이 소요되기 때문에 비효율적이다.
https://developer.apple.com/documentation/swift/array/removefirst(_:)

그래서 Stack 2개로 Queue를 구현해봤다.

큐 구현법 1 - 정석

1) inputStack, outputStack 을 정의한다.
2) enqueue - inputStack 에 삽입한다.
3) dequeue 는 다음 3가지 상황을 고려한다.

inputStack, outputStack 이 모두 비어있을 경우 : nil 리턴
outputStack이 비어있지 않은 경우 : outputStack 에서 popLast()
outputStack이 비어있지만 inputStack이 비어있지 않은경우 :
inputStack 이 빌때까지 모두 outputStack으로 pop 수행 후, outputStack에서 popLast()

하지만 Swift 에서는 비어있는 array에서 popLast()를 수행시 자동으로 nil을 반환하므로 위 3가지 상황을 고려하지 않고 편하게 코드를 작성해도 된다.

import Foundation

struct Queue<T> {
    var inputStack = [T]()
    var outputStack = [T]()
    
    mutating func append(_ x: T) {
        inputStack.append(x)
    }
    
    mutating func pop() -> T? {
        var top: T?
        while !(inputStack.isEmpty) {
            let x = inputStack.popLast()!
            outputStack.append(x)
        }
        top = outputStack.popLast()
        return top
    }
    
    mutating func head() -> T? {
        while !(inputStack.isEmpty) {
            let x = inputStack.popLast()!
            outputStack.append(x)
        }
        return outputStack.isEmpty ? nil : outputStack[outputStack.endIndex-1]
    }
    
    func isEmpty() -> Bool {
        return inputStack.isEmpty && outputStack.isEmpty ? true : false
    }
}


var q = Queue<Int>()

시간복잡도
- append : O(1)
- pop : 상황에따라 O(1) or O(N)

큐 구현법 2 - reversed 활용

swift 공식문서를 읽어보면 reverse()는 O(N) 소요, reversed 는 O(1) 소요된다.
https://developer.apple.com/documentation/swift/array/reversed()

따라서 swift의 reversed 를 활용하면 append와 pop모두 O(1) 소요되는 큐를 구현할 수 있다.

import Foundation

struct Queue<T> {
    var inputStack = [T]()
    var outputStack = [T]()
    
    mutating func append(_ x: T) {
        inputStack.append(x)
    }
    
    mutating func pop() -> T? {
        var top: T?
        if outputStack.isEmpty {
            outputStack = inputStack.reversed()
            inputStack.removeAll()
            top = outputStack.popLast()
        }
        else {
            top = outputStack.popLast()
        }
        return top
    }
    
    mutating func head() -> T? {
        if outputStack.isEmpty {
            outputStack = inputStack.reversed()
            inputStack.removeAll()
        }
        return outputStack.isEmpty ? nil : outputStack[outputStack.endIndex-1]
    }
    
    func isEmpty() -> Bool {
        return inputStack.isEmpty && outputStack.isEmpty ? true : false
    }
}


var q = Queue<Int>()

알고리즘 풀 때는 이 Queue를 사용해야겠다.

[힙 Heap]

소스 코드

import Foundation

public struct Heap<T> {
    // 전체 노드
    var nodes: [T] = []
    // 비교 연산자
    let comparer: (T,T) -> Bool

    var isEmpty: Bool {
        return nodes.isEmpty
    }

    // 예를 들어, Heap<Int>(comparer: >=) 는 Min Heap
    init(comparer: @escaping (T,T) -> Bool) {
        self.comparer = comparer
    }

    // top 반환
    func top() -> T? {
        return nodes.first
    }

    // 삽입
    mutating func push(_ element: T) {
        var index = nodes.count

        nodes.append(element)

        while index > 0, !comparer(nodes[index],nodes[(index-1)/2]) {
            nodes.swapAt(index, (index-1)/2)
            index = (index-1)/2
        }
    }

    // 삭제
    mutating func pop() -> T? {
        guard !nodes.isEmpty else {
            return nil
        }

        if nodes.count == 1 {
            return nodes.removeFirst()
        }

        let result = nodes.first
        nodes.swapAt(0, nodes.count-1)
        _ = nodes.popLast()

        var index = 0

        while index < nodes.count {
            let left = index * 2 + 1
            let right = left + 1

            if right < nodes.count {
                if comparer(nodes[left], nodes[right]),
                    !comparer(nodes[right], nodes[index]) {
                    nodes.swapAt(right, index)
                    index = right
                } else if !comparer(nodes[left], nodes[index]){
                    nodes.swapAt(left, index)
                    index = left
                } else {
                    break
                }
            } else if left < nodes.count {
                if !comparer(nodes[left], nodes[index]) {
                    nodes.swapAt(left, index)
                    index = left
                } else {
                    break
                }
            } else {
                break
            }
        }

        return result
    }
}

extension Heap where T: Comparable {
    // 초기 설정을 해주지 않으면 Min Heap
    init() {
        self.init(comparer: >=)
    }
}

참고 : https://gist.github.com/JCSooHwanCho/a3f070c2160bb8c0047a5ddbb831f78e

힙 활용

파이썬에서는 heapq 를 지원하지만 swift 에서는 힙 자료구조를 기본 제공하지 않는다.
따라서 위의 소스 코드를 활용한다.

Heap 활용 코드

// Min Heap 세팅
var minHeap = Heap<Int>(comparer: >=)

// Max Heap 세팅
var maxHeap = Heap<Int>(comparer: <=)

// 100 삽입                                     
minHeap.push(100)

// 삭제
let _ = minHeap.pop()

// top 반환
let top = minHeap.top()

// heap 원소 개수
let heapCount = minHeap.nodes.count

[실수 다루기]

제곱, 제곱근

import Foundation

let x: Int = 5
let sqrtX = sqrt(Double(x))		// 제곱근
let powX = pow(Double(x), 2)	// 제곱

print(Int(sqrtX))	// 2
print(powX)			// 25.0

분수

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

[정렬]

조건 정렬

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: "Park", age: 27), 
Student(name: "kang", age: 25)]

// 나이 오름차순 정렬
let sortedStudentArray = studentArray.sorted(by: {$0.age < $1.age})

다중 조건 정렬

튜플의 특성을 이용해서 다중 정렬을 할 수 있다.

("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"]]

[반복문 응용]

Stride

for i in stride(from: 0, to: 7, by: 2) {
    print(i)
}
// 0, 2, 4, 6 출력

[고차함수]

map, filter, reduce

[Swift 고차함수 블로그에 정리했던 글]

// 기본 배열
let arr = [1,2,3,4,5,6,7,8]

// <filter>
// 짝수만 걸러내기
let evenFilter = arr.filter { (num) -> Bool in return num % 2 == 0}
print(evenFilter)

let evenFilter2 = arr.filter { $0 % 2 == 0 }
print(evenFilter2)


// <map>
// 문자열 타입으로 바꾸기
let toString = arr.map{ (num: Int) -> String in
    return "\(num)"
}
print(toString)

let toString2 = arr.map { "\($0)" }
print(toString2)


// <reduce>
// 모든 원소를 문자열에 담아 압축하기
let arrStr = arr.reduce ("") { (first, second) -> String in
    return "\(first)\(second)"
}
print(arrStr)

let arrStr2 = arr.reduce(""){ "\($0)\($1)" }
print(arrStr2)

[순열과 조합]

Combinations

Python 에서는 itertools 에서 combinations 를 제공해주지만 Swift 는 그런걸 제공해주지 않는다.

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)

https://wansook0316.github.io/cs/algorithm/2021/08/18/swift-algorithm-combination-permutation.html

Permutations

func permutation<T>(_ elements: [T], _ k: Int) -> [[T]] {
    var result = [[T]]()
    var visited = [Bool](repeating: false, count: elements.count)
    
    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)

https://wansook0316.github.io/cs/algorithm/2021/08/18/swift-algorithm-combination-permutation.html

[기타]

dropLast, popLast, removeLast

보통 Array 를 스택으로써 사용할 때 활용한다.

dropLast(n) : Array 를 변경하지는 않고, 마지막 n 개를 제외한 원소들 반환
popLast() : Array 의 마지막 원소를 제거해버리고, 남은 원소들 반환, 원소가 비어있을 시 nil 반환
removeLast(1) : Array 의 마지막 원소 n 개를 제거해버리고, 남은 원소들 반환, 원소가 비어있을 시 컴파일 에러

3가지 메서드 시간 비교

// 같은 역할이지만 다른 방법들의 시간 비교하기

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 {
    // put your func
    let arr2 = arr.dropLast(4)
}

// 2. index 슬라이싱 대입 -> 0.32 초
progressTime {
    // put your func
    let arr2 = arr[arr.startIndex..<arr.index(arr.startIndex, offsetBy: arr.endIndex - 4)]
}

// 3. popLast() 4번 -> 0.0002 초
progressTime {
    // put your func
    arr.popLast()
    arr.popLast()
    arr.popLast()
    arr.popLast()
}

// 4. removeLast(4) -> 0.0007 초
progressTime {
    // put your func
    arr.removeLast(4)
}

결론

"dropLast() or 인덱스 슬라이싱을 해서 할당하는 방법" 보다 "popLast() or removeLast()" 이 훨씬 빠르다.

popLast() 쓰자.

변수 여러 개 동시 선언

다음과 같이 튜플을 활용해서 변수 여러 개를 한 줄로 선언할 수 있다.

let (a, b, c): (Int, Int, Int) = (0, 1, 2)
print(a)	// 0
print(b)	// 1
print(c)	// 2

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: " "))
print(str.components(separatedBy: " "))
// ["a", "b", "c", "d", "e"]
// ["a", "b", "c", "d", "e", ""]

print(str2.split(separator: " "))
print(str2.components(separatedBy: " "))
// ["a", "b", "c", "d", "e"]
// ["a", "", "b", "", "c", "", "d", "", "e"]

백준 풀때 입력 빨리받기

https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88
백준에서 이걸 쓰면 시간초과 안나는 경우가 상당히 많다.
전형적인 Union Find 문제 소셜 네트워킹 어플리케이션 에서 체감할 수 있었다.
파이썬의 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
/*

[기억해둘 것]

1. Set 에는 튜플이 들어갈 수 없다.
Set<(Int, Int)> 는 불가능하다.

2. split(separator: " ") 대신 split{$0 == " "} 을 쓰자.

var str = "1 2 3"
// arr2 가 더 깔끔
let arr = str.split(separator: " ").map{Int(String($0))!}
let arr2 = str.split{$0==" "}.map{Int(String($0))!}

김상우

안녕하세요, iOS 와 알고리즘에 대한 글을 씁니다.

이전 포스트

[Python] 백준 13905번의 3가지 풀이 방법

다음 포스트

[CS] 데이터베이스

1개의 댓글

Hamp

2023년 9월 7일

좋은 글 보고 갑니다.

답글 달기