-
Notifications
You must be signed in to change notification settings - Fork 0
/
11000.swift
129 lines (109 loc) · 4.26 KB
/
11000.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
import Foundation
//문제풀이 당시 Heap 부분 구현이 난해해서 Heap 구현은 다른데서 제작한 코드를 사용함
struct MinHeap<T: Comparable> {
var heap: [T] = []
var isEmpty: Bool {
return heap.count <= 1 ? true : false
}
init() {}
init(_ element: T) {
heap.append(element) // 0번 index채우기 용
heap.append(element) // 실제 Root Node 채움.
}
mutating func counting() -> Int{
return heap.count-1
}
mutating func topValue() -> T{
return heap[1]
}
mutating func insert(_ element: T) {
if heap.isEmpty {
heap.append(element)
heap.append(element)
return
}
heap.append(element)
func isMoveUp(_ insertIndex: Int) -> Bool {
if insertIndex <= 1 { // Root Node일 때,
return false
}
let parentIndex = insertIndex / 2
return heap[insertIndex] < heap[parentIndex] ? true : false
}
var insertIndex = heap.count - 1
while isMoveUp(insertIndex) {
let parentIndex = insertIndex / 2
heap.swapAt(insertIndex, parentIndex)
insertIndex = parentIndex
}
}
enum moveDownStatus { case left, right, none }
mutating func pop() -> T? {
if heap.count <= 1 {
return nil
}
let returnData = heap[1]
heap.swapAt(1, heap.count - 1)
heap.removeLast()
func moveDown(_ poppedIndex: Int) -> moveDownStatus {
let leftChildIndex = poppedIndex * 2
let rightChildIndex = leftChildIndex + 1
// case1. 모든(왼쪽) 자식 노드가 없는 경우(완전이진트리는 왼쪽부터 채워지므로)
if leftChildIndex >= heap.count {
return .none
}
// case2. 왼쪽 자식 노드만 있는 경우
if rightChildIndex >= heap.count {
return heap[leftChildIndex] < heap[poppedIndex] ? .left : .none
}
// case3. 왼쪽&오른쪽 자식 노드 모두 있는 경우
// case3-1. 자식들이 자신보다 모두 큰 경우(자신이 제일 작은 경우)
if (heap[leftChildIndex] > heap[poppedIndex]) && (heap[rightChildIndex] > heap[poppedIndex]) {
return .none
}
// case3-2. 자식들이 자신보다 모두 작은 경우(왼쪽과 오른쪽 자식 중, 더 작은 자식을 선별)
if (heap[leftChildIndex] < heap[poppedIndex]) && (heap[rightChildIndex] < heap[poppedIndex]) {
return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
}
// case3-3. 왼쪽과 오른쪽 자식 중, 한 자식만 자신보다 작은 경우
if (heap[leftChildIndex] < heap[poppedIndex]) || (heap[rightChildIndex] < heap[poppedIndex]) {
return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
}
return .none
}
var poppedIndex = 1
while true {
switch moveDown(poppedIndex) {
case .none:
return returnData
case .left:
let leftChildIndex = poppedIndex * 2
heap.swapAt(poppedIndex, leftChildIndex)
poppedIndex = leftChildIndex
case .right:
let rightChildIndex = (poppedIndex * 2) + 1
heap.swapAt(poppedIndex, rightChildIndex)
poppedIndex = rightChildIndex
}
}
}
}
var ClassroomHeap : MinHeap<Int> = MinHeap()
let Session = Int(readLine()!)!
var Time = [[Int]]()
for _ in 1...Session{
Time.append(readLine()!.split(separator: " ").map { Int($0)! })
}
Time = Time.sorted(by: {$0[0] < $1[0]})
Time = Time.sorted(by: {($0[0] == $1[0])&&($0[1] < $1[1])})
ClassroomHeap.insert(Time[0][1])
for i in 1...Session-1{
if(Time[i][0] >= Int(ClassroomHeap.topValue())){
ClassroomHeap.pop()
ClassroomHeap.insert(Time[i][1])
}
else if(Time[i][0] < ClassroomHeap.topValue()){
ClassroomHeap.insert(Time[i][1])
}
}
print(ClassroomHeap.counting())