swift로 연결리스트 구현해보기

 

오늘 연결리스트라는 것을 새로 배운 기념으로..

https://www.acmicpc.net/problem/1158

어제 시간초과로 똥쌌던 위 문제를 연결리스트로 한 번 풀어봄

결과는 시간초과지만 연결리스트를 구현해본다는 것에 의미를 두었음

 

class Node<T> {
	var data: T?
	var next: Node?
	
	init(data: T?, next: Node? = nil) {
		self.data = data
		self.next = next
	}
}

class LinkedList<T> {
	var head: Node<T>?
	
	init(head: Node<T>?) {
		self.head = head
	}
	
	func append(data: T?) {
		if head == nil {
			head = Node(data: data)
			return
		}
		var node = head
		while node?.next != nil {
			node = node?.next
		}
		node?.next = Node(data: data)
	}
	
	func removeFirstNode() {
		if head == nil {
			return
		}
		head = head?.next
	}
	
	
}

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = input[0]
let k = input[1]

var list = LinkedList<Int>(head: nil)

for i in 1...n {
	list.append(data: i)
}

var result = [String]()

while result.count != n {
	for _ in 1..<k {
		list.append(data: list.head?.data)
		list.removeFirstNode()
	}
	result.append(String((list.head?.data)!))
}

print("<\(result.joined(separator: ", "))>")

 

제일 앞 노드를 삭제하는 것에 대해 시간이 O(1)만큼 걸리니까

어제 작성한 것처럼 메모리를 희생하지 않고 좀 빠르게 풀 수 있지 않을까? 하고 구현해봤는데

응 시간초과

리스트를 만들 때 append부분에서 결국 O(N)만큼 잡아먹고,

그걸 for 문 안에서 돌리니까 결국은 여기서 시간을 많이 잡아먹게 되는 것 같다.

 

 

연결리스트는 확실히 훑어보면서&&동시에 어떤 메서드를 처리하는(삽입이라던지 삭제라던지) 경우에만 사용하는 것이 좋은 듯 하다.

스위프트에 내장되어 있는 게 아니니까..

구현은 복잡한데 저런 경우를 제외하면 크게 메리트가 있지는 않은 듯 함.