[프로그래머스] Swift - 광고 삽입

https://school.programmers.co.kr/learn/courses/30/lessons/72414

프로그래머스

 

2023.08.15 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

• 전체 동영상 재생 시간 play_time
• 광고 재생 시간 adv_time
• 시청자들의 재생 기록 logs

이 데이터들이 주어졌을 때 광고를 언제 배치해야 사람들이 가장 많이 보는지를 구하는 문제입니다.

 

1. 우선 logs를 바탕으로 각 시간대별로 시청자 수가 몇 명인지 구한다. ➡️ 배열에 초 단위로 기록
2. 1번에서 구한 시청자 수를 바탕으로 어떤 구간에 시청자가 가장 많은지 구한다.
3. 2번에서 구한 구간이 광고가 들어갈 구간이다.

이렇게 순차적으로 아이디어를 떠올렸습니다.

 

먼저, 1번 요구사항인 각 시간대에서의 시청자 수를 구해야 합니다.

이 부분이 가장 중요했으며 사실 유사한 문제가 많이 있는데, 바로 누적합을 사용하여 해결하면 되는 문제입니다.

 

시청자의 수를 누적합 대상으로 지정하고 logs를 순회하며 시청이 발생하면 해당 시각에 +1 시청이 끝나면 -1을 기록하면 됩니다.

그리고 logs 순회가 끝나면 누적합 요소들을 기록한 배열을 한번 쭉 순회하며 누적합을 진행하면 됩니다.

배열 viewerCntByTime 배열을 만들어 각 초에 시청중인 시청자의 수를 기록한다고 생각하면 viewerCntByTime[3]은 영상의 3초에 시청 중인 사람의 수를 의미합니다.

 

2번 작업은 슬라이딩 윈도우 알고리즘을 사용하면 됩니다.

큰 배열에서의 고정된 크기의 부분 배열의 합을 구하면 되기 때문입니다.

 

문제에서는 장황하게 광고 영상의 누적 시간을 직접 구하고 있지만 사실 이렇게 할 필요 없이 광고가 들어갈 구간을 시청 중인 사람의 수를 구하면 됩니다.

해당 구간의 사람의 수가 가장 많다면 당연히 광고 영상의 누적 재생시간도 가장 크기 때문입니다.

즉, 광고의 재생 시간을 구하는 문제가 아니라 부분 배열(서브 배열)의 합의 최댓값을 구하는 문제로 생각하고 풀면 됩니다.

 

부분 배열의 크기가 고정이기 때문에 슬라이딩 윈도우 알고리즘을 사용하여 O(N)으로 합이 최댓값인 구간을 구할 수 있습니다.

그리고 이 구간의 시작 시간이 이 문제의 답입니다.

 

주의

문제에서 시간을 다루고 있기 때문에 시간을 관리할 때의 시작 지점과 끝 지점을 구간에 포함시킬 때 매우 주의해야합니다.

이 문제에서도 이 부분을 간과하고 있다가 로직은 맞는데 계속 실패 처리가 나와서 디버깅하는데 시간을 오래 썼습니다.

 

특히, 이 문제는 실행 시간, 종료 시간, 재생시간이 등장하는데 이 문제에서의 시간 개념을 잘 생각해야 했습니다.

 (제출하고 80.6점이 나온다면 이 부분을 고려하지 않았을 가능성이 높습니다.)

이렇게 문제에서 재생시간에 대한 정의를 내리고 있고, 우리는 광고 영상의 재생시간 동안의 최대 시청자 수를 구해야 합니다.

영상의 재생 시작 시각과 종료 시각을 배열의 인덱스로 생각해야 하는데 이 때 시작과 끝 구간을 설정할 때 끝 시간은 -1 처리를 해줘야 했습니다.

예를 들어 위의 예시와 유사하게 00시 00분 01초부터 00시 00분 05초까지 동영상이 재생되었다면 재생시간은 4초입니다.

배열을 생성할 때 다음과 같이 생각하면 안 됩니다.

초 (인덱스)	0	1	2	3	4	5
		시작 인덱스				끝 인덱스

재생 시간이 4초인 구간을 구할 때 arr[1...5]로 설정한다는 의미인데 이러렇게 하면 1,2,3,4,5의 인덱스가 더해져 총 5초의 재생시간으로 구해지기 때문입니다.

따라서 arr[1...4]나 arr[1..<5]로 계산해야 합니다.

초 (인덱스)	0	1	2	3	4	5
		시작 인덱스			끝 인덱스

 

 

풀이

1. 시간 변환 코드 구현

fileprivate extension String {
    var toSeconds: Int {
        let hourMinuteSecond = self.split(separator: ":")
        let hours = Int(hourMinuteSecond[0])!
        let minutes = Int(hourMinuteSecond[1])!
        let seconds = Int(hourMinuteSecond[2])!
        
        return hours*60*60 + minutes*60 + seconds
    }
}

fileprivate extension Int {
    var toHHMMSS: String {
        let hours = self/(60*60)
        let minutes = self%(60*60)/60
        let seconds = self%60
        return String(format: "%02d:%02d:%02d", hours, minutes, seconds)
    }
}

문제에서는 HH:MM:SS 형태의 문자열로 시간을 주지만 우리는 초 단위로 계산해야 편하기 때문에 String 형태의 시간을 Int로 바꾸는 코드와 역으로도 바꾸는 코드를 구현합니다.

 

2. solution 함수 구현

fileprivate func solution(_ play_time:String, _ adv_time:String, _ logs:[String]) -> String {
    let totalSeconds = play_time.toSeconds

    var prefixSum = Array(repeating: 0, count: totalSeconds+1)    // 시청자 수 누적합 기록
    
    for log in logs {
        let logArr = log.components(separatedBy: "-")
        let startTime = logArr[0].toSeconds
        let endTime = logArr[1].toSeconds
        
        prefixSum[startTime] += 1
        prefixSum[endTime] -= 1
    }
    
    var viewerCntByTime = Array(repeating: 0, count: totalSeconds+1) // 영상의 재생 시간에서의 시청자 수
    
    var sum = 0
    for i in viewerCntByTime.indices {
        sum += prefixSum[i]
        viewerCntByTime[i] = sum
    }
    
    let adTotalSeconds = adv_time.toSeconds
    var result = 0
    
    var currentAdViewerShip = viewerCntByTime[0...(adTotalSeconds-1)].reduce(0, +)
    var maxAdViewerShip = currentAdViewerShip  // 광고 시청자 수의 최댓값
    
    for adStartTime in 0...totalSeconds-adTotalSeconds {
        let adEndTime = adStartTime + adTotalSeconds - 1

        currentAdViewerShip = currentAdViewerShip - viewerCntByTime[adStartTime] + viewerCntByTime[adEndTime+1]
                
        if currentAdViewerShip > maxAdViewerShip {
            maxAdViewerShip = currentAdViewerShip
            result = adStartTime+1
        }
    }
    
    return result.toHHMMSS
}

prefixSum 배열에 누적합 대상을 기록합니다.

log를 순회하며 기록하는데 시청이 발생한 시각에 +1 끝난 시각에 -1을 해줍니다.

그 다음에 누적합 알고리즘을 수행하며 viewerCntByTime을 채워 나갑니다.

 

이제 크기가 adTotalSeconds인 부분 배열을 대상으로 위치를 1씩 이동시킵니다.

그러면서 부분 배열의 합의 최댓값인 순간에서의 시작 인덱스를 result로 정합니다.

 

합의 최댓값을 매번 직접 전부 더해서 구하면 시간 초과가 발생하기 때문에 기존 값을 저장하고 있다가 시작 인덱스에서의 값을 빼고 끝 인덱스를 1 더한 다음에 그 위치에서의 값을 더하면 이동한 위치에서의 합을 구할 수 있습니다. O(1) 입니다.

 

이 과정 전체는 O(N)입니다.

 

 

마무리

1. 누적합

2. 부분 배열의 합의 최댓값

3. 시간 데이터 핸들링

 

이렇게 총 3가지의 스킬이 필요했던 문제였습니다.

깡 구현 문제로 생각하게 되면 시간 복잡도가 너무 올라가는데 위의 3가지 요소를 잘 활용하면 O(N)으로만 구성된 풀이법으로 해결할 수 있었습니다.

 

다만, 시간의 구간을 고려할 때 종료 부분은 포함하지 않는 것을 생각하기 쉽지 않았습니다.

문제에서 노골적으로 시작 시간과 끝 시간을 시청에 포함시키는 것으로 설명하고 있기 때문에 스스로 그걸 거부하는 방식으로 문제를 푸는 것이 어려웠습니다.