코딩테스트를 위한 Swift 필수 자료구조 구현하기

 

Photo by ThisisEngineering on Unsplash

 

 

코딩테스트는 취업에 있어 꼭 필요한 과정 중 하나입니다. 저도 익숙하게 사용했던 Python 언어를 활용하여 코딩 테스트를 준비했었는데요. 하지만 최근에 점차 많은 회사들이 포지션에 맞게 코딩테스트 언어 제한을 두었습니다.

 

 

2021 네이버웹툰 개발 챌린지 ( iOS 포지션은 Swift를 사용해야 한다 )

 

 

Swift는 Type-Safe 언어이고 문법도 간결해서 iOS 개발할 때에 무척 편리하게 사용하고 있습니다. 하지만 Python과 달리 별도의 Built-in 자료 구조가 없어서 코딩테스트에 필요한 부분은 직접 구현해야 합니다.

 

이번 게시글에서는 Swift를 통해 필요한 자료구조를 직접 구현하는 방법에 대해 기술하고자 합니다.

 

 

 

 

Queue

Queue 는 FIFO 방식으로 동작하는 자료구조입니다. 프린터, 작업 대기열 같은 문제에 활용되고 더 나아가 SPFA 같은 최단 거리 알고리즘에 사용합니다.

 

Double Array를 활용한 Queue

	struct Queue<T> {
	private var input: [T] = []
	private var output: [T] = []
	var isEmpty: Bool {
	return input.isEmpty && output.isEmpty
	}
	var count: Int {
	return input.count + output.count
	}
	mutating func enqueue(_ val: T) {
	self.input.append(val)
	}
	mutating func dequeue() -> T? {
	if output.isEmpty {
	output = input.reversed()
	input.removeAll()
	}
	return output.popLast()
	}
	}

view raw DoubleArray_Queue.swift hosted with ❤ by GitHub

Swift Reversed 메서드의 시간 복잡도는 O(1) 이기 때문에 Double Array를 사용하면 쉽게 Queue를 구현할 수 있습니다. 일반적인 상황에서 주로 사용합니다.

 

Cursor를 활용한 Queue

	import Foundation
	struct Queue<T> {
	var input: [T] = []
	var cursor = 0
	var count: Int {
	return input.count - cursor
	}
	var isEmpty: Bool {
	return count == cursor
	}
	mutating func enqueue(_ value: T) {
	input.append(value)
	}
	mutating func dequeue() -> T? {
	guard cursor < input.count else { return nil }
	defer {
	cursor += 1
	if cursor >= 100 && cursor < input.count {
	input = Array(input[cursor..<input.count])
	cursor = 0
	}
	}
	return input[cursor]
	}
	}

view raw Cursor_Queue.swift hosted with ❤ by GitHub

Double Array를 활용한 Queue는 극단적인 테스트 케이스에서 시간초과가 발생하게 됩니다. ( 상당히 많은 1회 추가, 삭제를 반복하는 경우 Array 를 계속 재할당하는 오버헤드가 발생함 )

 

이런 경우에는 Cursor를 활용해서 Queue를 구현할 수 있습니다.

 

 

 

 

Heap ( Priority Queue )

힙(우선순위 큐)는 완전 이진트리를 기반으로 최소(혹은 최대) 값을 O(logN)으로 구할 수 있는 자료구조입니다. 최소, 최대 값을 지속적으로 추적해야 하는 문제나 최단거리를 구하는 다익스트라 알고리즘에 사용합니다.

 

	struct Heap<T> {
	private(set) var array = [T]()
	private var compare: (T, T) -> Bool
	var count: Int { return array.count - 1 }
	init(compare: @escaping ((T, T) -> Bool), intialValue: T) { // 초기화 용 변수
	self.compare = compare
	self.array.append(intialValue)
	}
	mutating func push(_ value: T) {
	array.append(value)
	float(self.count)
	}
	@discardableResult
	mutating func pop() -> T? {
	guard self.count > 0 else { return nil }
	let item = self.array[1]
	self.array[1] = self.array[self.count]
	self.array.removeLast()
	sink(1)
	return item
	}
	private mutating func float(_ targetIndex: Int) {
	var index = targetIndex
	while index / 2 > 0 {
	// 자식이 더 작다면
	if compare(self.array[index], self.array[index / 2]) {
	self.array.swapAt(index, index / 2)
	}
	index /= 2
	}
	}
	private func minChildIndex(_ targetIndex: Int) -> Int {
	let left = targetIndex * 2
	let right = targetIndex * 2 + 1
	if right > self.count { // 힙 사이즈 보다 크면 right 가 존재하지 않는다.
	return left
	} else if compare(array[left], array[right]) {
	return left
	} else {
	return right
	}
	}
	private mutating func sink(_ targetIndex: Int) {
	var index = targetIndex
	while index * 2 <= self.count {
	let minIndex = minChildIndex(index)
	// 큰 값이 아래로 내려가야 함
	if compare(array[minIndex], array[index]) {
	self.array.swapAt(index, minIndex)
	}
	index = minIndex
	}
	}
	}

view raw Heap.swift hosted with ❤ by GitHub

구현 편의를 위해 트리가 아닌 배열을 사용하고 첫번째 index 는 사용하지 않습니다.

 

 

 

Heap 구현이 꼭 필요하지 않은 경우

Heap에 대한 원리는 파악하고 있어야 하지만 실제 코딩테스트 환경에서 구현하는데 큰 부담이 있습니다.

 

 

1. 최대, 최소 값을 계속 추척해야하는 문제

-> 테스트 케이스 범위와 실행 시간이 여유롭다면 min, max 메서드로 코드를 작성해봅니다. 시간 복잡도에 큰 손해가 있지만 우선 동작에 초점을 맞춥니다.

-> 시간 초과가 발생하거나 시험 여유 시간이 남는다면 다시 Heap으로 리팩토링합니다.

 

 

2. 최단거리를 구하는 문제

-> 다익스트라 알고리즘 대신 SPFA 알고리즘을 사용합니다. SPFA는 Queue를 사용하기 때문에 구현에 큰 어려움이 없고 일반적인 상황에서 O(V+E)으로 동작합니다.

-> 다만 테스트 케이스가 까다롭다면 O(V*E)으로 동작하기 때문에 Heap을 사용하는 다익스트라 알고리즘으로 구현해야 합니다.

 

 

 

 

 

 

 

* leetcode를 통해 동작을 확인했지만 틀린부분이 있을 수 있습니다. 잘못된 부분은 말씀해주시면 감사하겠습니다.