[백준 20207] 달력 swift

https://www.acmicpc.net/problem/20207

20207번: 달력

골드5

 

문제

 

 

문제 풀이

연속된 구간의 가로와 세로를 구해야 한다.
그림을 통해 보는 게 빠를 것 같아 그려보았다.

 

먼저 각 일자에 해당하는 스케줄의 개수를 days 배열에 저장한다.

width는 0이 나오지 않는 연속된 개수를 구하면 되고 height는 해당 구간의 가장 max값이 높이가 된다.

 

 

코드

import Foundation

let n = Int(readLine()!)!
var schedules: [(start: Int, end: Int)] = []
for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map {Int(String($0))!}
    let start = input[0]; let end = input[1]
    schedules.append((start, end))
}

var days: [Int] = Array(repeating: 0, count: 367) // 1일 ~ 365일에 대해 각 스케줄의 개수를 갖는다.

for schedule in schedules {
    // ex) 2~4일 스케줄이면 2,3,4 인덱스에 +1
    for i in stride(from: schedule.start, through: schedule.end, by: 1) {
        days[i] += 1
    }
}

var width = 0
var height = 0
var answer = 0

for i in 1..<days.count {
    let day = days[i]
    // 0이 아닌 연속된 구간의 width를 구한다.
    if day > 0 {
        width += 1
        height = max(height, day) // 높이는 해당 구간의 최대 스케줄 개수
    }
    
    // 연속된 구간이 끝났으면
    else if day == 0 {
        answer += width*height
        width = 0
        height = 0
    }
}

print(answer)

 

 

후기

정렬하고 블럭들을 저장하고 붙이고... 매우 복잡한 방법만 생각해내다 가로는 구할 수 있는데 높이는 구하기가 까다로워 보였다. 

but 생각보다 간단한 아이디어로 풀 수 있어 정리해 보았다.