백준 - 수 정렬하기 3 (10989)

첫 번째 풀이

let file = FileIO()

let N = file.readInt()
var arr = [Int]()
var answer = ""
for _ in 0..<N {
    arr.append(file.readInt())
}

radixSort(&arr)
arr.forEach { answer += "\($0)\n" }

print(answer)

func radixSort(_ array: inout [Int]) {
    var output = Array(repeating: 0, count: N)
    var digit = 1
    for _ in 0..<5 {
        var bucket = Array(repeating: 0, count: 10)
        array.forEach {
            bucket[($0 / digit) % 10] += 1
        }
        for i in 1..<bucket.count {
            bucket[i] += bucket[i-1]
        }
        array.reversed().forEach {
            output[bucket[($0 / digit) % 10] - 1] = $0
            bucket[($0 / digit) % 10] -= 1
        }
        array = output
        digit *= 10
    }
}

계수 정렬 + 기수 정렬을 이용해서 코드를 짰는데 또 시간 초과 😇

실행 시간 줄이려고 파일 입출력 클래스도 쓰고 print문 사용도 한 번으로 줄였는데도 통과가 안 된다.

백준 진짜 싫다 ㅎㅎ

두 번째 풀이

import Foundation

final class FileIO {
    private let buffer: Data
    private var index: Int = 0
    
    init(fileHandle: FileHandle = FileHandle.standardInput) {
        self.buffer = try! fileHandle.readToEnd()! // 인덱스 범위 넘어가는 것 방지
    }
    
    @inline(__always) private func read() -> UInt8 {
        defer {
            index += 1
        }
        guard index < buffer.count else { return 0 }
        
        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)
    }

    @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 N = file.readInt()
var arr = Array(repeating: 0, count: 10001)
var answer = ""
for _ in 0..<N {
    arr[file.readInt()] += 1
}

for i in 1..<arr.count {
    if arr[i] > 0 {
        answer += String(repeating: "\(i)\n", count: arr[i])
    }
}

print(answer)

시간 초과 검색하다가 훨씬 간단한 풀이가 있길래 참고해서 풀었다.