문제 풀이 아이디어 (그리디)
체크인과 체크아웃을 나눈다.
현재의 입력은 체크인과 체크아웃이 하나의 배열 안에 묶어서 제공합니다. 필요한 방의 갯수를 구하기 위해서는 해당 입력을 체크인과 체크아웃으로 각각 나눌 필요가 있습니다. 그리고 해당 입력을 “시간 순”으로 정렬하는 것입니다.
필요한 방의 갯수를 세기
이제 체크인과 체크아웃에 관계 없이 시간 순으로 정렬했습니다. 이 배열을 순환하면서 체크인인 경우 빈방이 있으면 체크인을 빈방이 없으면 필요한 방을 하나 추가합니다. 체크아웃의 경우 빈방을 반납하면 될 것입니다.
주의할 점
청소 시간 추가하기
체크 아웃 시간에는 청소 시간을 10분 추가해야 합니다.
정렬할 때 시간이 같은 경우
시간 순으로 정렬할 때 시간이 동일하다면 체크 아웃이 앞으로 오도록 해야 합니다. 빈방에 바로 체크인할 수 있기 때문입니다.
코드
// string으로 표현된 시간을 int로 파싱하는 함수
func time(from string: String) -> Int {
let h = Int(string.prefix(2))!
let m = Int(string.suffix(2))!
return h * 60 + m
}
// 체크인 혹은 체크아웃을 나타내는 객체
struct Event: Comparable {
// 체크인인 경우 true
let isIn: Bool
// 시간
let time: Int
// 시간 순으로 정렬하기 위한 < 정의
static func < (lhs: Event, rhs: Event) -> Bool {
// 시간이 다른 경우 시간이 작은 것이 앞으로
if lhs.time != rhs.time {
return lhs.time < rhs.time
// 시간이 같은 경우
// 둘 다 in인 경우 -> 상관 없음
// 둘 다 out인 경우 -> 상관 없음
// 하나는 in, 다른 것은 out인 경우 -> out이 먼저 (out한 방에 in이 같은 시간에 들어갈 수 있으므로)
// 따라서 rhs.isIn이 true인 경우 <, false인 경우는 >
} else {
return rhs.isIn
}
}
}
func solution(_ book_time:[[String]]) -> Int {
// 시간을 int로 파싱하고 나가는 시간에는 청소시간 10분을 더해준다.
let bookTime = book_time.map { $0.map { time(from: $0) } }.map { [$0[0], $0[1] + 10] }
// 주어진 체크인, 체크아웃 시간을 각각 하나의 Event 객체로 바꾸어준다
var events = [Event]()
for time in bookTime {
let checkIn = Event(isIn: true, time: time[0])
let checkOut = Event(isIn: false, time: time[1])
events.append(checkIn)
events.append(checkOut)
}
// Event 객체를 정렬 (시간순, 시간이 같은 경우 out이 먼저)
events.sort()
// 필요한 방의 수
var ans = 1
// 현재 남은 방의 수
var vacancy = 1
for event in events {
// 1. 현재 event가 체크인인 경우
if event.isIn {
// 1-1. 빈방이 있는 경우: 빈방 - 1
if vacancy > 0 {
vacancy -= 1
// 1-2. 빈방이 없는 경우: 방이 하나 더 필요함
} else {
ans += 1
}
// 2. 현재 event가 체크 아웃인 경우: 방을 비움
} else {
vacancy += 1
}
}
return ans
}문제 풀이 아이디어 (수직선)
이번에는 수직선을 활용해서 한번 더 풀어보도록 하겠습니다. 시간의 입력이 1분 단위로 들어오므로 하루를 1분 간격의 수직선으로 표현합니다.
그리고 수직선에 해당 시간 (분 단위)에 투숙하는 투숙객을 표시합니다.
모든 투숙객을 표시한 이후에는 수직선에서 가장 큰 수가 필요한 방의 수가 됩니다.
코드
// string으로 표현된 시간을 int로 파싱하는 함수
func time(from string: String) -> Int {
let h = Int(string.prefix(2))!
let m = Int(string.suffix(2))!
return h * 60 + m
}
func solution(_ book_time:[[String]]) -> Int {
// 시간을 int로 파싱하고 나가는 시간에는 청소시간 10분을 더해준다.
let bookTime = book_time.map { $0.map { time(from: $0) } }.map { [$0[0], $0[1] + 10] }
// 수직선: 하루 1440분 + 청소시간 10분
var timeLine = Array(repeating: 0, count: 1450)
// 수직선에 해당 시간에 존재하는 투숙객 표시
for time in bookTime {
for i in time[0]..<time[1] { //👉 청소시간의 마지막 시간에는 체크인 할 수 있으므로 마지막 시간은 표시하지 않음
timeLine[i] += 1
}
}
// 수직선 상의 가장 큰 수 = 동시에 투숙하는 손님의 최댓값 = 필요한 방의 수
return timeLine.max()!
}코드 + (누적합을 사용)
수직선에 투숙객을 표시할 때 반복문을 사용하면 이중반복문을 사용해서 실행시간이 오래 걸립니다. (이 문제는 book_time이 최대 1,000이고 체크인, 아웃의 시간 차이도 최대 1450뿐이라서 큰 문제는 없습니다만…) 이처럼 수직선에 여러 개의 범위를 표현할 때 “누적합”이라는 기법을 사용하면 이중 반복문 없이 구현할 수 있습니다.
누적합은 범위의 시작점에 1, 끝점에 -1을 각각 표시합니다. 모든 범위의 표시가 끝났다면 수직선의 i는 i - 1까지 모든 수의 합이 되도록 반복문을 실행하면 됩니다.
// string으로 표현된 시간을 int로 파싱하는 함수
func time(from string: String) -> Int {
let h = Int(string.prefix(2))!
let m = Int(string.suffix(2))!
return h * 60 + m
}
func solution(_ book_time:[[String]]) -> Int {
// 시간을 int로 파싱하고 나가는 시간에는 청소시간 10분을 더해준다.
let bookTime = book_time.map { $0.map { time(from: $0) } }.map { [$0[0], $0[1] + 10] }
// 수직선: 하루 1440분 + 청소시간 10분
var timeLine = Array(repeating: 0, count: 1450)
// 누적합: 시작점에 +1, 끝점에 -1 표시
for time in bookTime {
timeLine[time[0]] += 1
timeLine[time[1]] -= 1
}
// 누적합: i는 i - 1까지의 합
for i in 1..<timeLine.count {
timeLine[i] += timeLine[i - 1]
}
// 수직선 상의 가장 큰 수 = 동시에 투숙하는 손님의 최댓값 = 필요한 방의 수
return timeLine.max()!
}