[Swift] 2021 KAKAO BLIND RECRUITMENT 광고 삽입

Problem

 

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

---

Solution

 

핵심

 

1. 모든 시간을 초로 환산하기

 

총 재생시간, 광고 시간, 시청자들이 재생을 시작한 시간, 시청자들이 재생을 끝낸 시간을 모두 초로 환산합니다.

 

ex) 총 재생시간이 1시간 11분 11초 이라면 -> 60분 11분 11초 -> 3600초 + 660초 + 11초 = 4271초

 

(아래 Source Code에서 makeSeconds 함수를 참고해주세요.)

 

2.총 플레이 시간을 초로 환산한 갯수에 +1만큼을 0을 넣은 값으로 배열 만들기(최대 360001개) 

 

ex) 총 재생시간이 1시간 11분 11초 이라면 4271초이므로 [0,0,0,0,0.....] 4272개 길이의 배열을 만들어줌.

 

(아래 Source Code에서 allPlaySeconds 변수를 참고해주세요.)

 

3.로그안에 있는 시작과 끝을 위에서 만든 배열에 표시해주기

 

시작하는 숫자의 인덱스에 +1을 해주고 끝나는 숫자의 인덱스에 -1을 해줍니다.

 

ex) 시청자가 2초부터 5초까지 봤다면 2번째와 5번째 인덱스 -> [0,0,1,0,0,-1]

 

(아래 Source Code에서 for log in logs를 참고해주세요.)

 

4. 총 플레이 시간 배열에 시청자들의 수 정하기

 

현재 인덱스를 현재 인덱스 숫자와 현재 인덱스 -1의 숫자를 더해줍니다.

 

이렇게 하면 모든 시청자들의 시작과 끝은 각각 +1 -1이 되어있으므로 그 사이에 있는 값은

 

누적된 값으로 됩니다.

 

ex) 예를 들면 시청자 A가 2초부터 10초까지 재생했고 B가 3초부터 7초까지 재생했다면

 

A = [0,0,1,0,0,0,0,0,0,0,-1] B = [0,0,0,1,0,0,0,-1]

 

둘을 합치면 [0,0,1,1,0,0,0-1,0,0,-1] 과 같이 될 것입니다.

 

그리고 이것을 위와 같이 현재 인덱스 숫자와 그 전 숫자를 합쳐주면

 

[0,0,1,2,2,2,2,1,1,1,0] 와 같이 될 것입니다.

 

그러면 정확히 A와 B가 겹친 시간은 3초 ~7초 즉 4초이므로 3,4,5,6 인덱스가 2로 되어있습니다.

 

(아래 Source Code에서 for i in 1...playTimeSeconds 을 참고해주세요.)

 

5.0초부터 광고시간까지 총 플레이 시간 배열에서 합 구해주기

 

0초부터 광고를 시작했을 경우가 가장 최소 시작이므로 0초부터 광고시간까지의 합을 구해 최소시작의 합을 만들어줍니다.

 

(아래 Source Code에서 sum 변수를 참고해주세요.)

 

5.광고시간부터 총 플레이시간까지 1초씩 움직이며 가장 최대의 합 구해주기

 

0초부터 광고시간까지 , 1초부터 광고시간+1까지,2초부터 광고시간 +2까지....이렇게 플레이시간까지의 합을 구해나가다 보면

 

가장 합이 높은 구간을 찾을 수 있습니다.

 

효율성을 위해선 모든 합을 구할 필요없이 구해져있는 합에서 가장 첫번째를 빼주고 가장 마지막의 + 1번째 값을 더해주기만 하면 됩니다.

 

ex) 0초부터 10초까지라면 그 다음 구간은 1초부터 11초이므로 0초를 빼주고 11초를 더해주면 그 다음번째 합이 됩니다.

 

(아래 Source Code에서 for i in advTimeSeconds..<playTimeSeconds를 참고해주세요.)

 

주의할 점

 

최대 30만 시청자가 최대 100시간까지 모두 볼 수 있으므로 초로 계산하면 36만 * 30만 = 1080억이 최대가 됩니다.

 

Int형,Float형 대신 Double을 사용해야 합니다.

---

Source Code

 

 

 

---

P.S

 

처음에 모든 누적 숫자를 구하려고 할때 로그를 아래와 같이 구했더니 한 8개 테스트케이스에서 시간 초과가 났다.

 

카카오 블로그에서 문제 풀이를 보고 시작과 끝에 +1을 해주고 -1을 해준 뒤 현재와 그 전 숫자를 더해주면

 

각 초에 시청자들의 수를 쉽게 구할 수 있었다. 

 

    for log in logs {

        let startEnd = splitPlaytime(playtime: log)
        let start = makeSeconds(time: startEnd.0)
        let end = makeSeconds(time: startEnd.1)

        for i in start..<end {
            allPlaySeconds[i] += 1
        }

    }

---

Reference

 

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설