[BOJ] 백준 10866 덱 (Swift)

문제

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

10866번: 덱

풀이

Deque 자료구조를 사용해서 풀 수 있습니다.

Deque 자료구조를 구현한 후, 명령에 맞게 처리해주면 됩니다.

Deque 자료구조에 대해 잘 모른다면, 이 포스팅을 참고하시면 도움이 될 것입니다.
https://dev-mandos.tistory.com/195

[자료구조] Deque에 대해 알아보고 구현해보기 (Swift)

소스코드

	struct Deque<T> {
	private var leftArray: [T] = []
	private var rightArray: [T] = []
	private var leftIndex: Int = 0
	private var rightIndex: Int = 0
	var isEmpty: Bool {
	return leftIndex + rightIndex >= leftArray.count + rightArray.count
	}
	var size: Int {
	return (leftArray.count + rightArray.count) - (leftIndex + rightIndex)
	}
	var front: T? {
	if isEmpty {
	return nil
	}
	if leftIndex >= leftArray.count {
	return rightArray[rightIndex]
	}
	return leftArray.last
	}
	var back: T? {
	if isEmpty {
	return nil
	}
	if rightIndex >= rightArray.count {
	return leftArray[leftIndex]
	}
	return rightArray.last
	}
	mutating func pushLeft(_ element: T) {
	leftArray.append(element)
	}
	mutating func popLeft() -> T? {
	if isEmpty {
	return nil
	}
	if leftIndex >= leftArray.count {
	let element = rightArray[rightIndex]
	rightIndex += 1
	return element
	}
	return leftArray.popLast()
	}
	mutating func pushRight(_ element: T) {
	rightArray.append(element)
	}
	mutating func popRight() -> T? {
	if isEmpty {
	return nil
	}
	if rightIndex >= rightArray.count {
	let element = leftArray[leftIndex]
	leftIndex += 1
	return element
	}
	return rightArray.popLast()
	}
	}
	enum Command: String {
	case pushFront = "push_front"
	case pushBack = "push_back"
	case popFront = "pop_front"
	case popBack = "pop_back"
	case size, empty, front, back
	}
	let n = Int(readLine()!)!
	var deque = Deque<Int>()
	for _ in 0..<n {
	let input = readLine()!.split(separator: " ")
	let command = Command(rawValue: String(input[0]))!
	switch command {
	case .pushFront:
	let element = Int(input[1])!
	deque.pushLeft(element)
	case .pushBack:
	let element = Int(input[1])!
	deque.pushRight(element)
	case .popFront:
	if let removed = deque.popLeft() {
	print(removed)
	} else {
	print(-1)
	}
	case .popBack:
	if let removed = deque.popRight() {
	print(removed)
	} else {
	print(-1)
	}
	case .size:
	print(deque.size)
	case .empty:
	print(deque.isEmpty ? 1 : 0)
	case .front:
	if let front = deque.front {
	print(front)
	} else {
	print(-1)
	}
	case .back:
	if let back = deque.back {
	print(back)
	} else {
	print(-1)
	}
	}
	}

view raw 덱.swift hosted with ❤ by GitHub

후기

insert, removeFirst 메서드를 사용하여 비효율적으로 구현해도 통과가 되는 문제이지만,
효율적인 Deque 자료구조를 구현해서 풀이하는 것이 Deque을 이해하는데 있어 도움이 될 것입니다.