Open ghis22130 opened 3 years ago
시간초과 ㅂㄷㅂㄷ...😡 시간초과되서 퀵정렬도 써봤는데 또 초과뜨네요
import Foundation
var count = Int(readLine()!)!
var schoolHoursArray = [[Int]]()
for _ in 1...count {
let schoolHours = readLine()!.split(separator: " ").map{Int($0)!}
schoolHoursArray.append(schoolHours)
}
func quickSort(_ array: [[Int]]) -> [[Int]] {
if array.count < 2 {
return array
} else {
let pivot = array[0][0]
let less = array.filter { $0[0] < pivot }
let greater = array.filter { $0[0] > pivot }
return quickSort(less) + [array[0]] + quickSort(greater)
}
}
schoolHoursArray = quickSort(schoolHoursArray)
var answer = 0
while !schoolHoursArray.isEmpty {
var endTime = schoolHoursArray[0][1]
schoolHoursArray.remove(at: 0)
while schoolHoursArray.contains(where: {$0[0] >= endTime}) {
for schoolHours in schoolHoursArray.enumerated() {
if endTime <= schoolHours.element[0] {
schoolHoursArray.remove(at: schoolHours.offset)
endTime = schoolHours.element[1]
break
}
}
}
answer += 1
}
print(answer)
@zeke-iOS 우선순위 큐 찾아봐야 할듯 물론 스위프트에서는 구현되있지 않음 ^__^ 지크꺼 while문 O(n^2) 라 시간 초과 나는 거일꺼에용..
문제 로직은 간단하니까 우선순위 큐가 뭐다정도만 이해하고 넘어가도 무방할듯..
대기업 공통 코테가 아닌이상 스위프트 코테에 이련 시련이 없기를ㅎ
https://www.acmicpc.net/problem/11000