Swift 백준 10989번) 수 정렬하기 3

수 정렬하기 3 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

5 초 (하단 참고)

8 MB (하단 참고)

181655

42018

31577

23.468%

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1 복사

1
1
2
2
3
3
4
5
5
7

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: cgiosy
• 문제의 오타를 찾은 사람: joonas

 

코드

import Foundation

let N = Int(readLine()!)!
var arr = [Int]()

for _ in 0..<N {
    arr.append(Int(readLine()!)!)
}

var resArr = arr.sorted()

for i in 0..<N{
    print(resArr[i])
}

당연히 sort를 사용하여 푸는 문제라고 접근하여서 풀었더니 시간초과만 주구장창 나왔다...

N의 범위가 N(1 ≤ N ≤ 10,000,000) 이니 입력을 받을때와 print를 할때 시간이 오래걸리는것을 알았지만~

그다음은 생각을 못하였다..

 

https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88

ps할 때 입력을 한꺼번에 받기 위한 유틸리티 클래스. fread의 swift 버전.

검색후 입력을 야무지게 받을수 있는것을 찾았고..(정말 감사합니다 ㅠㅠ)

새로운 결과 배열을 추가하지않고 String에 줄바꿈을 하며 +하기로 하였다.

 

최종코드

import Foundation

final class FileIO {
    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 file = FileIO()

let N = file.readInt()
var arr = Array(repeating:0,count:10001)

for _ in 0 ..< N {
    let i = file.readInt()
    arr[i] += 1
}

var res = ""

for i in 1...10000 {
    res += String(repeating:"\(i)\n",count:arr[i])
}
print(res)