[swift] 백준 - 1931번: 회의실 배정

1931번: 회의실 배정

---

문제 푸는 데 있어 도움이 되도록 나의 풀이와 개선된 풀이를 올립니다.
또한 풀이 후 다른 사람의 풀이를 보고 참고할만한 풀이도 올립니다.
- 문제에 따라 나의 풀이만 있을 수 있습니다.
- 해당 풀이들은 풀이 중 하나일 뿐 최선의 풀이는 아닐 수 있습니다.

 

나의 풀이

let meetingCount = Int(readLine()!)!
var time = (0..<meetingCount).map { _ in readLine()!.split(separator: " ").map { Int($0)! }}.sorted { $0[1] < $1[1] }
var endTime = time[0][1]
var count = 1
while true {
    let temp = time.filter { $0[0] >= endTime }
    if temp.isEmpty { break }
    time = temp
    endTime = temp[0][1]
    count += 1
}
print(count)

 

주의!! 오답 풀이입니다.

시간초과로 오답이 나옵니다.

 

요즘 탐색과 알고리즘의 종류를 더 공부하고

문제를 풀어야겠다는 생각이 듭니다.

 

완전탐색으로 풀 경우

문제에서 최적의 알고리즘을 요구하는 경우가 많아

시간제한에 걸리네요.

 

이번 문제는

다른 사람의 풀이를 보고

시간 복잡도에 초점을 맞춰

공부해 보겠습니다.

 

---

개선된 풀이

let meetingCount = Int(readLine()!)!
var time = (0..<meetingCount).map { _ in readLine()!.split(separator: " ").map { Int($0)! }}
time.sort { $0[1] < $1[1] || $0[1] == $1[1] && $0[0] < $1[0] }
var endTime = -1
var count = 0
for i in time {
    if i[0] >= endTime {
        endTime = i[1]
        count += 1
    }
}
print(count)

// 시간: 약 164ms

 

일단 시간을 줄여 통과했습니다.

 

개선 부분 1

time 변수를 만들 때

고차함수를 계속 이어서 나열했었는데요

 

var time = (0..<meetingCount).map { _ in readLine()!.split(separator: " ").map { Int($0)! }}.sorted { $0[1] < $1[1] }

time.sort { $0[1] < $1[1] || $0[1] == $1[1] && $0[0]

 

이렇게 말이죠

근데 여기서 sorted에 삼항연산자를 쓸려고 하니 에러가 발생했습니다.

그래서 따로 정렬 부분은 빼줬습니다.

해당 개선은 문제의 시간복잡도와 상관은 없었습니다.

 

 

개선 부분 2

여기서 시간복잡도를 해결했는데요.

while문 안에 filter를 넣으니

while반복이 될 때마다 time배열을 전부 완전탐색 했던 게

시간초과의 원인이었습니다.

 

그래서 개선 부분 1에 정렬 조건을 추가했던 건데요.

정렬로 원하는 순서를 다 맞추고 나니

배열의 완전탐색을 반복할 일이 없어졌습니다.

 

---

참고할만한 풀이

import Foundation

final class FileIO {
    
    @inline(__always) private var buffer: [UInt8] = Array(FileHandle.standardInput.readDataToEndOfFile()) + [0], byteIdx = 0
    
    @inline(__always) private func readByte() -> UInt8 {
        defer { byteIdx += 1 }
        return buffer.withUnsafeBufferPointer { $0[byteIdx] }
    }
    
    @inline(__always) func readInt32() -> Int32 {
        var number: Int32 = 0, byte = readByte(), isNegative = false
        while byte == 10 || byte == 32 { byte = readByte() }
        if byte == 45 { byte = readByte(); isNegative = true }
        while 48...57 ~= byte { number = number * 10 + Int32(byte - 48); byte = readByte() }
        return number * (isNegative ? -1 : 1)
    }
}

let file = FileIO()
let n = Int(file.readInt32())

var times = [(Int32, Int32)]()
for _ in 0..<n {
    times.append((file.readInt32(), file.readInt32()))
}

times.sort {
    if $0.0 == $1.0 { return $0.1 < $1.1 }
    return $0.0 < $1.0
}

var index = 0
var lhs = times.first!
var count = 1

while index < n-1 {
    let rhs = times[index+1]
    
    if lhs.1 <= rhs.0 {
        lhs = rhs
        count += 1
    } else if lhs.1 >= rhs.1 {
        lhs = rhs
    }
    
    index += 1
}

print(count)

// 시간: 40ms

 

시간을 40ms까지 줄인 코드를 가져와봤습니다.

 

정확이 뜻을 해석하기는 힘들지만

메모리를 적게 차지하는 타입으로 강제해

시간을 줄인 거 같습니다.

 

---