백준 1946 신입 사원

출처: www.acmicpc.net/problem/1946

분류: 그리디

---

접근방식

다른 사람보다 서류와 면접 점수가 모두 낮은 경우엔 탈락, 합격한 사람의 수를 구하는 문제입니다.

서류 1등은 무조건 합격입니다. 1등보다 면접 등수마저 낮다면 그 사람은 탈락이 되겠죠.

이때 1등의 면접 등수가 서류 2등 ~ 나머지 사람의 합격을 가르는 기준점이 됩니다.

 

1등의 면접 점수보다 낮은 사람을 모두 거르고 나면 남아있는 사람 중 서류 1등이 다시 합격의 기준점이 되죠.

이를 반복해주면 합격자의 수를 구할 수 있습니다.

하지만 이렇게 해주면 시간 초과가 납니다. (Swift 기준) 매번 나머지를 다시 도는건 너무 비효율적인 방법이죠.

 

보다 효율적으로 해결할 수 있는 방법이 있습니다.

서류 1등의 면접 등수를 기준점으로 해서

그 다음으로 합격된 사람 중 1등의 면접 등수보다 높은 경우가 나타나면 이 사람으로 기준점만 바꿔주면 됩니다.

우선 서류를 기준으로 오름차순 정렬을 하고나면 차례대로 돌면서 기준점을 바꿔주면서 커트해주면 됩니다.

 

해결방법

 

swift에서 그냥 readline을 사용하면 시간초과가 나서 라이노님의 FileIO 방법을 사용해 수정했습니다.

돌아다니는 코드는 많은데 라이노님의 FileIO 원본 글을 찾지 못하겠네요.. 
라이노님 블로그 주소라도 남깁니다,, (감사합니다.)

import Foundation

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 testcase = file.readInt()

for _ in 0..<testcase {
    let candidatorCount = file.readInt()
    var scores = [[Int]]()
    for _ in 0..<candidatorCount {
        let scoreInput = [file.readInt(), file.readInt()]
        scores.append(scoreInput)
    }
    scores.sort { $0[0] < $1[0] }
    
    var interviewCutline = scores[0][1]
    var passedCount = 1
    for candidator in 1..<candidatorCount {
        if scores[candidator][1] < interviewCutline {
            interviewCutline = scores[candidator][1]
            passedCount += 1
            
            if interviewCutline == 1 {
                break
            }
        }
    }
    
    print(passedCount)
}

 

[재채점으로 시간초과 - 21.10.02 확인]

위 설명 그대로입니다. 오름차순 정렬 후 기준점을 바꿔주면서 합격자 수를 체크합니다.

for _ in 0..<Int(readLine()!)! {
    var pass = 1
    var candidators = [[Int]]()
    for _ in 0..<Int(readLine()!)! {
        let scores = readLine()!.split(separator: " ").map { Int($0)! }
        candidators.append(scores)
    }
    
    candidators.sort { (c1, c2) -> Bool in
        return c1[0] < c2[0]
    }
    
    var min = candidators[0][1]
    
    for i in 1..<candidators.count {
        if min > candidators[i][1] {
            min = candidators[i][1]
            pass += 1
        }
    }
    
    print(pass)
}

 

시간 초과가 났던 풀이입니다.

// 시간초과
for _ in 0..<Int(readLine()!)! {
    var pass = 0
    var candidators = [[Int]]()
    for _ in 0..<Int(readLine()!)! {
        let scores = readLine()!.split(separator: " ").map { Int($0)! }
        candidators.append(scores)
    }

    candidators.sort { (c1, c2) -> Bool in
        return c1[0] < c2[0]
    }

    while !candidators.isEmpty {
        pass += 1
        let passCandi = candidators[0]
        var newCandi = [[Int]]()

        for i in 1..<candidators.count {
            if passCandi[1] > candidators[i][1] {
                newCandi.append(candidators[i])
            }
        }
        candidators = newCandi
    }
    print(pass)
}

 

감사합니다 :)