1946 swift - 신입 사원 / 시간 초과 해결

Greedy 사용

[Swift] Greedy / 그리디 / 탐욕 알고리즘

---

지원자의 서류심사 성적으로 sort하면 O(NlogN)으로 maxInterviewRank로 where절을 사용해서 아래와 같은 코드로 2NlogN의 시간을 가지고 문제를 풀 수 있지만, 아래의 코드는 백준의 Swift 의 느린 입력으로 인해 시간초과를 받을 수 밖에 없다

let T = Int(readLine()!)!
for _ in 0..<T {
	let N = Int(readLine()!)!
	var applicants = [[Int]]()
	for _ in 0..<N {
		let score = readLine()!.split{$0==" "}.map{Int(String($0))!}
		applicants.append(score)
	}
	applicants.sort{$0[0] < $1[0]}
	
	var maxInterviewRank = applicants.first![1]
	var count = 1
	for i in 1..<N where applicants[i][1] < maxInterviewRank {
		count += 1
		maxInterviewRank = applicants[i][1]
	}
	print(count)
}

 

FileIO를 Int부분만 잘라내어 사용해서 파일 입력속도를 향상 시켜주었다.

import Foundation

final class IntIO {
	private let buffer:[UInt8]
	private var index: Int = 0
	
	init(fileHandle: FileHandle = FileHandle.standardInput) {
		buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)]
	}
	
	@inline(__always) private func read() -> UInt8 {
		defer { index += 1 }
		return buffer[index]
	}
	
	@inline(__always) func readInt() -> Int {
		var sum = 0
		var now = read()
		var isPositive = true
		
		while now == 10 || now == 32 { now = read() }
		if now == 45 { isPositive.toggle(); now = read() }
		while now >= 48, now <= 57 {
			sum = sum * 10 + Int(now-48)
			now = read()
		}
		
		return sum * (isPositive ? 1:-1)
	}
}

let io = IntIO()

let T = io.readInt()
for _ in 0..<T {
	let N = io.readInt()
	var applicants = [[Int]]()
	for _ in 0..<N {
		let applicationRank = io.readInt(), interviewRank = io.readInt()
		applicants.append([applicationRank, interviewRank])
	}
	applicants.sort{$0[0] < $1[0]}
	
	var maxInterviewRank = applicants.first![1]
	var count = 1
	for i in 1..<N where applicants[i][1] < maxInterviewRank {
		count += 1
		maxInterviewRank = applicants[i][1]
	}
	print(count)
}