· 아이디어💡
이 문제에 접근 방법은 두 가지가 있다. 하나는 큐를 구현해서 푸는 방법과 큐를 구현하지 않고 푸는 방법이 있다. 결론적으론 두 방법 다 같은 원리로 접근해서 푸는 방법이긴 하다. 포인터 큐를 사용할 예정인데, dequeue를 하면 front라는 제일 처음 인덱스를 +1을 계속해줌으로 써 dequeue를 한 배열은 배제하고 그 이후 인덱스부터 확인하는 방법이다. 큐를 구현하지 않고 푸는 방법도 같은 원리를 사용하는 방법이다.
· 코드 😵😵💫
1. 큐를 구현해서 푸는 방법
struct QueuePointer<T> {
private var elements: [T] = []
private var front = 0
var isEmpty: Bool {
elements.count < front + 1
}
var count: Int {
elements.count - front
}
func peek() -> T? {
front < elements.count ? elements[front] : nil
}
mutating func enqueue(with element: T) {
elements.append(element)
}
@discardableResult
mutating func dequeue() -> T? {
if !isEmpty {
defer { front += 1 }
return elements[front]
} else {
return nil
}
}
}
func sol2164() {
let cards = Int(readLine()!)!
var list = QueuePointer<Int>()
for i in 1...cards {
list.enqueue(with: i)
}
while list.count != 1 {
list.dequeue()
list.enqueue(with: list.dequeue()!)
}
print(list.dequeue()!)
}
sol2164()
2. 큐 없이 푸는 방법
func sol2164() {
let n = Int(readLine()!)!
var front = 0
var cards: [Int] = []
for i in 1...n {
cards.append(i)
}
while cards.count - front > 1 {
front += 1
cards.append(cards[front])
front += 1
}
print(cards[front])
}
sol2164()
· 시간 복잡도 ⁉️🤔
시간복잡도는 O(N)이다. 이 문제는 O(N^2)으로 풀 수 없다. 시간초과가 발생하기 때문이다.
· 고려사항 🌟
언어에 따라 Queue 라이브러리가 있으면 빠르게 풀 수 있고, 없다면 직접 구현하든지 혹은 그 원리를 사용해서 풀면 된다.
'# 개발 > 알고리즘' 카테고리의 다른 글
[알고리즘] Swift 정렬 (0) | 2024.04.25 |
---|---|
[알고리즘] Swift - 토마토(백준7576) (0) | 2024.04.21 |
[알고리즘] Swift - 올바른 괄호(백준9012) (0) | 2024.04.16 |