문제 링크

문제 풀이 아이디어

수직선 + 누적합 👍

이렇게 연속된 시간 or 공간에 대해서 다룰 때는 이 포스팅(시간) 혹은 이 포스팅(공간)에서 사용한 수직선 + 누적합을 활용하면 시간복잡도를 O(N^2)에서 O(N)로 줄일 수 있습니다. 수직선의 길이인 play_time이 최대 100시간이므로 초로 환산하면 360,000이므로 logs의 크기가 300,000이므로 O(M*N)보다는 O(N)의 복잡도를 가지는게 최선이겠지요. (여기서 M은 play_time, N은 logs의 크기)

두 가지 풀이

누적합 한번 더!

이제 수직선에 시간이 모두 표시되었으므로 해당 수직선에서 최적의 광고 위치를 찾으면 됩니다. 그렇게 하기 위해서는 0부터 시작해서 광고시간에 해당되는 길이 만큼의 수직선의 수의 합들을 비교해야 하는데요.

매번 일일히 구하는 것은 시간초과가 나올 가능성이 높습니다. 저는 여기에서도 한번 더 누적합을 활용했는데요. 다시 해당 수직선에 누적합을 구해줍니다. 그렇게 하면 수직선의 [i]는 (0초 ~ i초)의 모든 시청자들의 합이 됩니다.

이 누적합을 활용해서 i에서 시작해서 advTime의 길이만큼 시청한 사람들의 길이를 탐색하면 O(N)으로 최댓값을 구할 수 있습니다.

투 포인터

고전적인(?) 투포인터 방법입니다. 일단 0초로 시작해서 advTime의 길이만큼 시청한 시작점과 끝점을 1칸씩 이동하면서 시작점은 빼주고, 끝점은 더해주면서 최댓값을 구하면 됩니다. 역시 O(N)으로 구할 수 있습니다.

주의할 점❗️

시작 이상, 끝 미만

예를 들어 0초에서 10초 사이에 영상을 시청한 경우 영상의 시청한 시간은 9초입니다. 따라서 영상을 시청한 사람들을 수직선에 표시할 때는 9칸에만 표시를 해야 합니다. 저는 시작 시간을 포함하고 끝 시간을 제외했습니다. 따라서 누적합을 기록할 때 “times[e + 1] -= 1”이 아니라 “times[e] -= 1”로 기록했습니다.

마찬가지로 누적합을 활용한 계산이나 투포인터를 활용할 때도 시작점과 끝점을 신경써서 계산해야 합니다.

시청 시간이 같다면?

시청 시간이 같다면 최댓값을 갱신하면 안됩니다. 같은 시청시간이라면 더 이른 시간대를 골라야하기 때문입니다.

String(format:)

마지막에 답을 String으로 출력할 때, String(format:)을 사용하면 원하는 format의 String을 만들 때 유용하게 사용할 수 있습니다. 1이라는 Int를 “01”라는 String으로 바꿀 때 복잡한 if문이나 삼항연산자 없이 구현할 수 있습니다.

코드

누적합 2번 사용한 풀이

import Foundation

// 시간 파싱 String -> Int
func parseTime(_ timeString: String) -> Int {
    let hms = timeString.split(separator: ":").map { Int($0)! }
    return hms[0] * 3600 + hms[1] * 60 + hms[2]
}

func parseTime(_ time: Int) -> String {
    let hour = time / 3600
    let min = (time % 3600) / 60
    let sec = time % 3600 % 60
    // %02d: 정수(d)를 2자리 출력을 하는데 빈 부분은 0으로 채워서
    return String(format: "%02d:%02d:%02d", hour, min, sec)
}

func solution(_ play_time:String, _ adv_time:String, _ logs:[String]) -> String {
    
    let playTime = parseTime(play_time)
    let advTime = parseTime(adv_time)
    
    // 수직선 만들기
    var times = Array(repeating: 0, count: playTime + 1)
    
    // 수직선에 시청 정보 기록 (시작점에 1, 끝점에 -1)
    for log in logs {
        let se = log.split(separator: "-").map { parseTime(String($0)) }
        let s = se[0], e = se[1]
        times[s] += 1
        times[e] -= 1
    }
    
    // 누적합 연산 -> times[i] = i시간에 시청한 시청자의 수
    for i in 1..<times.count {
        times[i] += times[i - 1]
    }
    
    // 누적합 연산 1번 더 -> times[i] = (0 ~ i)시간 동안 시청한 시청자의 수
    for i in 1..<times.count {
        times[i] += times[i - 1]
    }
    
    var ans = 0
    var sum = times[advTime - 1]
    
		for i in 1..<(times.count - advTime) {
        // times[i + advTime - 1] - times[i - 1]
            // = (i ~ i + advTime)시간 동안 시청한 시청자의 수
            // = i부터 시작해서 advTime 길이 만큼 시청한 시청자 수
        if sum < times[i + advTime - 1] - times[i - 1] { //👉 기존 합보다 크면 업데이트
            sum = times[i + advTime - 1] - times[i - 1]
            ans = i
        }
    }
    
    return parseTime(ans) // 시작시간을 파싱해서 리턴
}

투 포인터 사용한 풀이

import Foundation

// 시간 파싱 String -> Int
func parseTime(_ timeString: String) -> Int {
    let hms = timeString.split(separator: ":").map { Int($0)! }
    return hms[0] * 3600 + hms[1] * 60 + hms[2]
}

func parseTime(_ time: Int) -> String {
    let hour = time / 3600
    let min = (time % 3600) / 60
    let sec = time % 3600 % 60
    // %02d: 정수(d)를 2자리 출력을 하는데 빈 부분은 0으로 채워서
    return String(format: "%02d:%02d:%02d", hour, min, sec)
}

func solution(_ play_time:String, _ adv_time:String, _ logs:[String]) -> String {
    
    let playTime = parseTime(play_time)
    let advTime = parseTime(adv_time)
    
    // 수직선 만들기
    var times = Array(repeating: 0, count: playTime + 1)
    
    // 수직선에 시청 정보 기록 (시작점에 1, 끝점에 -1)
    for log in logs {
        let se = log.split(separator: "-").map { parseTime(String($0)) }
        let s = se[0], e = se[1]
        times[s] += 1
        times[e] -= 1
    }
    
    // 누적합 연산 -> times[i] = i시간에 시청한 시청자의 수
    for i in 1..<times.count {
        times[i] += times[i - 1]
    }
    
    // 시작점이 0인 시청시간의 총합
        // 시작 0, 끝 s + advTime - 1
    var s = 0
    var sum = 0
    for i in s...(s + advTime - 1) {
        sum += times[i]
    }

    var highest = sum
    var ans = s

    // 시작점 + 1, 끝점 - 1하면서 합이 더 크면 갱신
    while s + advTime - 1 < playTime {
        sum -= times[s]
        s += 1
        sum += times[s + advTime - 1]
        if sum > highest {
            ans = s
            highest = sum
        }
    }
    
    return parseTime(ans) // 시작시간을 파싱해서 리턴
}