기본 Swift에는 Python의 collections.deque가 없다.
Python에서는 collections.deque 덕분에 스택, 큐, 데크의 모든 연산을 O(1)의 시간 복잡도로 빠르게 처리할 수 있다.
그렇다면 Swift에서도 알고리즘 문제를 효율적으로 풀기 위해,
Deque 자료구조를 직접 하나 구현해두면 기본적인 큐/스택/데크 의 연산을 해결할 수 있당
데크는 주로 연결 리스트로 만드는데, 여기서는 스택 2개를 활용해보도록 하겠다.
참고로 Swift에서도
Collections라이브러리가 있다고 한다...! 링크
import Collections var deque: Deque<String> = ["Ted", "Rebecca"] deque.prepend("Keeley") deque.append("Nathan") print(deque) // ["Keeley", "Ted", "Rebecca", "Nathan"]하지만 사용이 불가능한 상황이 있을 수 있기도 하고 학습용으로 한번 구현해보기로.
어떻게 구현?
말로 한번 정리해보자. 일반 Array에서 앞에다가 집어넣고 빼고 하면 무조건 시간복잡도가 O(n)이 되기 때문에 일반적인 방법으로는 안된다.
대신 앞쪽, 뒤쪽 두 개의 배열을 생성한다.
dequeArray: 앞쪽 전용enqueArray: 뒤쪽 전용
1) push
pushFirst는 dequeArray에 append 한다. 여기서, 물리적으로 배열의 맨 앞에 넣는 게 아니라 그냥 append해서 뒤로 넣는다.pushLast는 enqueArray에 append 한다.
2) pop
pop 할 때가 중요하다.
참고로 여기서 ❗️논리적 허점❗️이 있다. 더 밑에 기술할 예정.
2-1) popFirst
- dequeArray에 값이 있을 경우, dequeArray에서 pop을 한다. 물리적으로 dequeArray에서 뒤에 있는 값이, 논리구조상 가장 앞에 있는 값이기 때문이다.
- dequeArray에 값이 없는 경우, enqueArray에서 맨 앞에 녀석을 Pop 해야 한다. 하지만 일반적으로 pop을 한다면 다시 시간복잡도가 O(n)이 될 것이다.
✔️ 여기서 reversed를 사용하게 되는데, Swift에서 reversed는 배열을 진짜로 뒤집어서 위치를 바꾸는 것이 아니다. 단순히 인덱스를 거꾸로 순회하도록 하는 view를 반환할 뿐이다.
=> reversed의 시간복잡도는 O(1)이다.
=> 단순히 enqueArray.reversed해서 popFirst를 한다면 시간복잡도가 O(1)이 되는 것이다.
reversed를 좀 더 부연 설명하면,
let arr = [1, 2, 3] let rev = arr.reversed()이렇게 한다고 배열이 복사가 되지는 않는다. 메모리상에서 rev는 arr을 참조하고, rev에 접근하면 arr의 인덱스를 뒤에서부터 접근하여 거꾸로 읽을 뿐이다. '읽기 전용'이 된다는 뜻.
하지만 다음과 같이 배열에 담아버리면,let copied = Array(arr.reversed())여기서는 완전한 복사가 발생하여 새로운 배열을 만들고, 시간복잡도가 O(n)이 된다.
결국 필요 없다는걸 조금 나중에 알게 됐지만...
2-2) popLast
popFirst와 반대로 생각하면 된다.
- enqueArray에 값이 있는 경우, 그냥 pop을 한다.
- enqueArray에 값이 없는 경우, dequeArray를 reversed해서 pop을 한다. 물리구조상 dequeArray에서 가장 앞에 있던 값이 논리구조상 가장 뒤에 있기 때문이다.
구현해보자.
struct Deque<T> {
var dequeArray = [T]()
var enqueArray = [T]()
mutating func pushFirst(k: T) {
dequeArray.append(k)
}
mutating func pushLast(k: T) {
enqueArray.append(k)
}
mutating func popFirst() {
if dequeArray.isEmpty {
let arr = enqueArray.reversed()
}
}
}여기까지 구현해보다 막혔다. 위에서 쓴 ❗️논리적 허점❗️이 여기서 나왔다.
enqueArray를 뒤집어서 pop 해서 값을 출력하는것까지는 문제가 없다. 그런데 실제로 enqueArray에서 값을 제거 하려면 결국 새 배열을 만들던 deque에 복사하던 뒤집어진 배열을 복사해야 하고, 그렇게 되면 시간복잡도가 다시 O(n) 으로 돌아가는 것이다.
dfs, bfs 하면서 코드로 보기만 했던 인덱스 이동을 이래서 하는구만 하고 깨달았음.
실제로 값을 제거하는 것이 아니라, 인덱스를 이동해서 제거된 것처럼 보이게 하는 것이다.
그러면 인덱스를 추가해서 논리를 좀 더 보완해보자.
어떻게 구현? 보완
1) push
는 그대로 간다.
2) pop
미리 배열을 적당한 크기로 만들어 놓고 반 잘라서 앞뒤를 나눌수도 있지만,
나는 일단 앞 배열(dequeArray) 과 뒷 배열(enqueArray)로 나누는 구조는 그대로 채택해서 가겠다.
이제 reversed는 필요 가 없다.
대신,
dequeIndex: dequeArray에서 몇개나 pop이 됐는지 관리enqueIndex: enqueArray에서 몇개나 pop이 됐는지 관리
를 사용한다.
2-1) popFirst
- dequeArray에
(여기서부터 슬슬 dequeArr, dequeIdx등 줄임말을 쓸 걸 후회된다.)값이 있을 경우, 정확히 말하면 물리적 값이 아닌 논리적 값이 남아있을 경우, 위와 그대로 간다. dequeArray.popLast를 한다는 뜻..isempty()가 아니라 dequeArray.count > dequeIndex 인지 확인해야 한다는 뜻이다.
- dequeArray에 값이 없을 경우, enqueArray에서 논리적 위치로 맨 앞에 있는 값을 출력하고 그것을 제거해야 한다. 하지만 실제로 제거할 수는 없으니, enqueIndex += 1을 해준다. 이후 또 다시 Pop을 한다면 enqueArray[1]의 값을 출력하고, enqueIndex += 1을 해준다 ... 결국, enqueArray[enqueIndex]을 출력하고, 계속 enqueIndex += 을 해주면 된다.
2-2) popLast
popFirst의 반대로 하면 된다. 이제 쓰기 힘들다.
다시 구현해보자 - [백준: 28279. 덱 2] 풀이
import Foundation
struct Deque<T> {
// stored property
var dequeArray = [T]()
var enqueArray = [T]()
var dequeIndex = 0
var enqueIndex = 0
// computed property
var isEmpty: Bool {
return dequeArray.count <= dequeIndex && enqueArray.count <= enqueIndex
}
var count: Int {
return dequeArray.count - dequeIndex + enqueArray.count - enqueIndex
}
// push
mutating func pushFirst(k: T) {
dequeArray.append(k)
}
mutating func pushLast(k: T) {
enqueArray.append(k)
}
// pop
mutating func popFirst() -> T? {
if isEmpty {
return nil
}
if dequeArray.count <= dequeIndex {
let first = enqueArray[enqueIndex]
enqueIndex += 1
return first
}
return dequeArray.popLast()
}
mutating func popLast() -> T? {
if isEmpty {
return nil
}
if enqueArray.count <= enqueIndex {
let last = dequeArray[dequeIndex]
dequeIndex += 1
return last
}
return enqueArray.popLast()
}
}참고로 여기서 기술했던 것처럼 배열의 크기가 커지면 메모리를 위해 일정 간격으로 .removeFirst()를 이용해 잘라줘야 하는데, 문제풀이에 지장이 없어 일단 뺐다.
++
또 참고로,
computed Property로 작성되는 기준은 Swift API Design Guide - Conventions에 설명되어 있는데,
Document the complexity of any computed property that is not O(1). People often assume that property access involves no significant computation, because they have stored properties as a mental model. Be sure to alert them when that assumption may be violated.
즉 계산량이 거의 없고, 내부 상태 기준으로 간단히 판단할 수 있는 경우에는 computed property를 쓰는 것이 자연스럽다는 것이다. 이런 기준에 따라, isEmpty, count처럼 시간복잡도가 O(1)이고 side effect도 없는 경우엔 computed property로 만드는 것이 권장된다고 한다. 궁금해서 찾아봄.
