[Swift 알고리즘] 18258 큐2 - 개빡침🤬 (feat. 더블 스택 큐 구현방법)

×

큐

백준 18258 큐2

Swift 에 회의감이 들게 하는 문제다,, 

계속 시간초과 뜨는데 아무리 다양한 방식으로 구현해봐도 내 코드는 어디가 문제인지 전혀 모르겠고,, 

알고리즘 구현을 잘못해서 발생하는 문제는 아닌거같은데 Swift 입출력이 느려서 그렇다나뭐라나 아무튼 개빡침,,

FileIO 사용해서 어케어케 하면 통과시켜주는듯,, 

 

백준에서는 시간초과로 통과를 안시켜주지만 Swift에서 더블스택을 사용하여 큐를 구현했을 때 생기는 의문점이 있어 공유해본다. 

보통 시간복잡도가 O(n)인 removeFirst()를 사용하지 않고 dequeue를 효율적으로 구현하는 방식으로 다음 두 가지를 흔히 사용한다.

1. 포인터를 사용한 큐 구현 

2. 더블 스택 큐

를 제시한다. 

 

1. 포인터 사용

removeFirst()를 사용하여 배열을 계속 변경하는 대신, 없애고 싶은 첫 원소를 계속 nil로 바꿔주면서 첫 원소의 index 값을 저장하여 dequeue를 구현하는 방식이다. 

first 라는 Int형 변수를 만들어, 맨 앞 원소의 index 값을 넣어준다. 

dequeue를 할 때, 맨 앞 원소를 nil로 만들고 first 변수 +1을 해주어 다음 첫 원소의 인덱스 값을 저장한다.

guard let element = queue[first] else { return nil }
queue[first] = nil //맨 앞 원소를 nil로 만들기
first += 1 //첫 원소 index +1
return element

하지만 이 방법의 경우, 배열의 크기가 커질수록 메모리 문제가 생길 수 있어

적절한 때에 nil로 dequeue된 n개를 removeFirst(n) 해서 사용해야 한다. 

 

2. 더블 스택 큐

O(1)의 시간복잡도를 가지는 popLast() 를 사용하기 위해 스택 두개를 사용하여 큐를 구현하는 방식이다. 

배열 두 개를 만들어 enqueue 는 rightStack.append 로, dequeue 는 leftStack.popLast() 를 사용하여 구현해준다. 

dequeue를 할 때 leftStack이 비어있는 경우, rightStack 을 거꾸로 뒤집은 배열을 넣어주고 rightStack을 비워준다.

if leftStack.isEmpty {
    leftStack = rightStack.reversed()
    rightStack.removeAll()
}
return leftStack.popLast()

여기서 의문점이 생긴 게, reversed() 의 시간복잡도가 O(1) 이라 빠르다(?) 라고 잘못 언급된 블로그들이 꽤 있어서 혼란스러웠다. 

reversed() 의 공식문서를 찾아보면 배열이 아닌 ReversedCollection<Self> 형태의 래퍼 형식을 반환한다.

배열로 바로 변환해주는 것이 아니라 래퍼형식으로 반환하기 때문에 O(1)의 시간복잡도를 가지게 되는데,

하지만 위 코드에서의 reversed() 는 O(1)이 아니라, 뒤집은 배열로 바로 변환을 하기 때문에 아마도 O(n)의 시간복잡도를 가질 것이다. 

또한 그 다음에 쓰이는 removeAll() 메서드도 O(n)의 시간복잡도를 가진다. 

 

그렇다면 O(n)의 시간복잡도를 가지는 .reversed() 와 .removeAll() 메서드를 사용하는 이 dequeue 방식이 어째서 O(1)의 시간복잡도를 가진다고 말할 수 있나? 잠시 의문을 가지게 되었다. 

이는 leftStack 이 비어있는 특정 경우에만 O(n) 의 시간복잡도가 사용이 되고, 일반적으로는 .popLast() 만 사용이 되어 O(1) 의 시간복잡도에 수렴한다고 볼 수 있다. 

 

 

---

이 문제 관련해서 공감가는 글 있어서 그냥 퍼와봄

 

 

https://velog.io/@rarebook92/%EB%B0%B1%EC%A4%80%EC%9D%80-Swift%EC%97%90%EA%B2%8C-%EA%B4%80%EB%8C%80%ED%95%B4%EB%9D%BC

백준은 Swift 시간초과에 관대해줘라

https://velog.io/@rarebook92/%EB%B0%B1%EC%A4%80%EC%9D%80-Swift-%EC%8B%9C%EA%B0%84%EC%B4%88%EA%B3%BC%EC%97%90-%EA%B4%80%EB%8C%80%ED%95%B4%EC%A4%98%EB%9D%BC-ver.2

백준은 Swift 시간초과에 관대해줘라 ver.2