백준 - 신입사원(Swift)

백준 - 신입사원(Swift)

 

 

 문제 설명

 

https://www.acmicpc.net/problem/1946

1946번: 신입 사원

 

 나의 풀이

 

 

서류시험이나 면접시험 둘 중 하나의 기준으로 먼저 정렬을 시키는데 이렇게 하면 뒤에있는 값은 항상 앞에 있는 값보다 1개 이상 뒤쳐지기 때문에 카운트가되려면 앞에 있는 값의 나머지 값(정렬되지 않은 값)보다 높아야한다.

 

주의할 점은 나머지 값은 진행될때마다 순위가 높아지면 가장 높은 순위를 갱신시키고 진행 해야한다는 것이다.

 

그리고 이 문제를 풀면서 readLine으로는 풀 수 없다는 것도 알게되었다. readLine은 한 줄씩 읽게되는데 이는 입력값이 100,000개가 넘어가면 시간초과가 일어났다. 

 

그래서 대안으로 라이노님의 FileIO를 이용해서 버퍼를 이용해서 문제를 해결해야한다. 

버퍼는 CPU와 입출력장치간의 차이를 최소화시키기위해서 사용하는 임시적인 공간이며, CPU에서 입출력장치의 요구를 즉각적으로 호출하는 것보다 버퍼에서 데이터를 모았다가 한번에 처리하는 것이 효율적이기 때문에 버퍼를 사용하는 것으로 알고있다. (정확하지는 않습니다💧)

 

import Foundation

// 라이노님의 FileIO
final class FileIO {
    private var buffer:[UInt8]
    private var index: Int
    
    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
        index = 0
    }
    
    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }
        
        return buffer.withUnsafeBufferPointer { $0[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)
    }
    
    @inline(__always) func readString() -> String {
        var str = ""
        var now = read()
        
        while now == 10
                || now == 32 { now = read() } // 공백과 줄바꿈 무시
        
        while now != 10
                && now != 32 && now != 0 {
            str += String(bytes: [now], encoding: .ascii)!
            now = read()
        }
        
        return str
    }
}
let file = FileIO()
let tc = file.readInt()

for _ in 0..<tc {
    var arr: [(Int, Int)] = []
    var cnt = 1
    let n = file.readInt()
    for _ in 0..<n {
        arr.append((file.readInt(), file.readInt()))
    }
    arr.sort(by: {$0.1 < $1.1})
    var min = arr[0].0
    for i in 1..<arr.count {
        if arr[i].0 < min {
            min = arr[i].0
            cnt += 1
        }
    }
    print(cnt)
}