[백준(BOJ)] 2075 N번째 큰 수 - 스위프트(Swift)

[Silver II] N번째 큰 수 - 2075

문제 링크

성능 요약

메모리: 149928 KB, 시간: 680 ms

분류

자료 구조, 우선순위 큐, 정렬

문제 설명

N×N의 표에 수 N²개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

12	7	9	15	5
13	8	11	19	6
21	10	26	31	16
48	14	28	35	25
52	20	32	41	49

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

출력

첫째 줄에 N번째 큰 수를 출력한다.

 

풀이

i)

2차원 배열을 1차원 배열로 변경하고 정렬한 뒤에, N번째 큰 수를 출력하면 되지 않을까,,?라고 생각하였습니다.

N이 1500까지이기 때문에 sort()를 사용해도 시간 제한에 안걸리지 않을 것 같았습니다,,

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

for _ in 0..<N {
    let row = readLine()!.split(separator: " ").map { Int($0)! }
    arr.append(row)
}

var heap = arr.flatMap { $0 }.sorted()

print(heap[N*N - N])

→ 시간 초과

• arr.append(row) : O(n * m) : split을 사용하여 각 줄을 나누는 부분이 시간 복잡도를 증가시킵니다.
• flatMap : O(m+n) (m: 결과의 길이, n: 배열의 길이)
• sorted(): O(n log n)

최악의 경우 O(n*m log n*m)까지 갈 수 있기 때문에 시간 초과가 나타나는 것입니다.

 

ii)

readInt()를 통해 값을 불러오면 해결될 것 같아서 사용하였습니다.

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)
    }

    @inline(__always) func readString() -> String {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
    }

    @inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return Array(buffer[beginIndex..<(index-1)])
    }
}


let fIO = FileIO()

let N = fIO.readInt()
var arr = [Int]()

for _ in 0..<N*N {
    let input = fIO.readInt()
    arr.append(input)
}
arr.sort()
print(arr[N*N-N])

 

Swift는 PS를 풀 때 시간 제한 등 파이썬과 같은 언어에 비해 좀 까다로운 것 같아 그만큼 열심히 공부를 해야할 것 같습니다,,