[Swift 알고리즘] 프로그래머스(Lv.3) - 광고 삽입 / 2021 카카오 블라인드

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.3) - 광고 삽입" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 광고 삽입

 

---

풀이

이번 문제는 구현 문제입니다. (아마?)

 

0. 모든 시간의 단위를 초로 통합합니다.

문제를 쉽게 해결하기 위해 단위를 초로 통합합니다.

100시간은 100 * 3600 = 360000이므로 문제 없습니다.

 

1. 입력된 play_time과 adv_time을 초로 변환합니다.

let times = time.split { $0 == ":" }.map { Int($0)! }
return times[0] * 3600 + times[1] * 60 + times[2]

: 로 나눠 초로 변환합니다.

메서드로 구현하여 모든 시간을 변환하는데 사용합니다.

 

2. play second 길이만큼 Double 배열을 만듭니다.

Int가 아닌 Double 배열을 만드는 이유는 최악의 경우 Int 범위를 넘기 때문입니다.

모든 사람이 100시간을 시청하면 로그 300000명 * 360000초 = 108000000000로 Int 범위를 넘습니다.

따라서 Double로 배열을 만듭니다. 이 배열을 시청자 수를 저장하는 역할입니다.

 

3. 로그를 파싱하여 시청자 수를 누적합니다.

시작 시간에 +1, 종료 시간에 -1을 합니다.

모든 로그에 대해 위 작업을 한 후 i 배열에 i-1 배열을 더합니다.

 

이러면 로그 각각에 대해 반복문을 돌리지 않고 O(N)의 시간복잡도로 시청자 수를 누적할 수 있습니다.

종이에 적어가며 확인해보시면 이해가 바로 되실 것입니다.

 

4. 큐의 원리를 이용해 구간 합을 구합니다.

구간 합은 그 구간에 시청 중인 사람 수입니다.

 

구간 합을 구하는 것도 최적화를 해야 합니다.

저는 처음에 범위에 대해 reduce를 해서 구간합을 구했는데 시간 초과를 만났습니다.

 

큐의 원리를 이용해 구간 합을 구합니다.

최초 1회만 구간합을 구하고 맨 앞 원소는 빼고 다음 원소를 더합니다.

그러면 구간합을 효율적으로 구할 수 있습니다.

 

5. 구간 합이 최대인 구간을 구합니다.

구간 합이 최대인 구간을 구해 return 합니다.

 

후기

최적화 방법에 대해 배울 수 있는 문제였습니다.

특히, 큐의 원리를 이용해 구간 합을 구하는 방법은 다른 곳에서도 유용하게 쓸 수 있을 것 같습니다.

시험에서 만났으면 울었을 것 같네요 ㅠㅠ

 

감사합니다!

---

전체 코드

import Foundation

func convertSec(_ time: String) -> Int {
    let times = time.split { $0 == ":" }.map { Int($0)! }
    return times[0] * 3600 + times[1] * 60 + times[2]
}

func convertTime(_ sec: Int) -> String {
    let hour = sec / 3600
    let min = (sec % 3600) / 60
    let sec = (sec % 3600 % 60)
    
    return String(format: "%02d:%02d:%02d", hour, min, sec)
}

func solution(_ play_time:String, _ adv_time:String, _ logs:[String]) -> String {
    var result = ""
    
    let playSec = convertSec(play_time) //초로 변환
    // print("playSec: \(playSec)")
    var counts: [Double] = Array(repeating: 0, count: playSec+1) //시청자 수 배열
    
    let advSec = convertSec(adv_time) ////초로 변환
    // print("advSec: \(advSec)")
    
    for log in logs {
        let times = log.components(separatedBy: "-")
        let start = convertSec(times[0])
        let end = convertSec(times[1])
        
        //시청자 수 계산 방법 -> 모든 로그에 대해 반복문을 돌리면 시간 초과
        //시작과 끝에 표시하고 반복 한 번에 계산 가능
        counts[start] += 1
        counts[end] -= 1
    }
    
    //들어오면 +1, 나가면 -1로 앞의 원소를 더하면 계산이 된다.
    for i in 1..<counts.count {
        counts[i] += counts[i-1]
    }
    
    var sum: Double = counts[0..<advSec].reduce(0, +)
    var maxSum: Double = sum
    result = convertTime(0)
    // print("time: \(result) / maxSum: \(maxSum)")
    for i in 0..<(counts.count-advSec) {
        sum = sum - counts[i] + counts[i+advSec] //앞에 하나 빼주고 뒤에 하나 넣어주고 -> Queue의 원리
        if sum > maxSum {
            maxSum = sum
            result = convertTime(i + 1) //지금 시작은 i+1임
            // print("sec: \(i) / time: \(result) / maxSum: \(maxSum)")
        }
    }
    
    return result
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.