[Swift 알고리즘] 백준 BOJ - 1946 신입 사원

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 1946 신입 사원" 문제를 풀었습니다.

 

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

1946번: 신입 사원

 

---

풀이

이번 문제는 그리디를 이용한 문제입니다.

 

알고리즘 자체는 어렵지 않습니다.

A 점수를 기준으로 오름차순으로 정렬합니다. 그러면 B 점수만 따져도 최적을 구할 수 있습니다.

B를 보면서 min 값이 갱신되는 횟수가 뽑을 수 있는 신입사원의 수와 동일합니다.

 

readLine()으로는 해결 할 수 없는 문제...

Swift의 readLine()으로는 해결할 수 없는 문제였습니다.

readLine() 자체가 시간이 오래 걸리는 편이라 어떻게 풀어도 시간 초과가 납니다.

따라서 파일에서 값을 읽는 방법을 사용해야 하는데요.

 

라이노님의 FileIO 클래스를 사용해보았습니다. 원본 글은 사라졌더라고요...

 

FileIO 인스턴스를 생성해 준 뒤

Int를 입력 받아야 하면 readInt()를, String은 readString()을 사용하면 됩니다.

 

---

전체 코드

//
//  main.swift
//  SwiftAlgorithm
//
//  Created by 유정주 on 2022/03/16.
//

//1946 신입 사원
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 count1 = file.readInt()
for _ in 0..<count1 {
    let count = file.readInt()
    var scores: [(Int, Int)] = []
    for _ in 0..<count {
        scores.append((file.readInt(), file.readInt()))
    }

    scores.sort { $0.0 < $1.0 }
    
    var result: Int = 1
    var min: Int = scores[0].1
    for i in 1..<scores.count {
        if scores[i].1 < min {
            result += 1
            min = scores[i].1
        }
    }
    print(result)
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.