문제
[프로그래머스][Python][2021 Kakao] 광고 삽입
풀이
카카오의 해설을 보고 이해한 내용을 정리하기 위해 작성하는 글이다.
문제 풀이
1. 시간을 초로 환산하기
HH:MM:SS 로 표현되는 모든 시간을 초로 환산한다.
문제에서 요구되는 계산(겹치는 시간 구하기 등)
을 용이하게 하기 위해서는 정수로 표현하는것이 편리하기 때문이며,
다뤄야 할 데이터의 범위를 계산하기도 쉽다.
영상의 최대 길이 99:59:59를 환산하면 1006060 1 359999이다.
이렇게 다뤄야 하는 데이터의 범위를 확인해보는것은
문제를 해결하기 위해 가능한 방법을 빠르게 판단해 볼 수 있는 습관인 것 같다.
359999라는 적당한 크기의 수에서 얻을 수 있는 힌트는
문제에서 주어진 범위내의 모든 시간을 초단위로 다룰 수도 있다는 것 정도이다.
아래와 같은 함수를 구현하여 입력으로 주어진 시간(문자열)을 초(정수)로 바꿔주었다.
def time_to_sec(time:str):
h, m, s = map(int, time.split(':'))
return s + m*60 + h*36002. 시청 시간의 구간합 구하기
문제에서 요구하는 것은,
영상의 재생시간 범위 내에 있는 임의의 시간 s 중에서
s ~ s adv_time 사이에 존재하는 영상 시청시간의 합이 최대인 s를 구하는 것이다.
일정 범위의 구간합을 구하기 위해서는 누적합을 이용할 수 있다.
여기서 일정 범위는 광고 시간의 길이가 될 것이며,
구간합은 범위 내에 존재하는 모든 시청시간의 합이 될 것이다.
따라서 누적합이 계산된 배열 T는 아래와 같아야 한다.
3. 초단위로 시청 기록의 수 구하기
그런데 배열 T를 구하기 위해서는 우선 각 구간의 시청 시간을 알아야 한다.
즉, 모든 시청 기록에 대해서 다음과 같은 표현이 가능해야 한다.
1초에서 5초까지의 시청기록이 왼쪽의 그림과 같이 존재한다고 할때,
오른쪽의 배열 A가 가지는 의미는 다음과 같다.
- A[x] = x초~x+1초 사이에 존재하는 시청 기록의 갯수
4. 범위내에 일정한 값을 더해주기
배열 A를 구하기 위해서는
logs를 순회하며,
초로 환산된 시청 시작시간 ~ 종료시간 사이의 위치에 1을 더해주면 된다.
하지만 이렇게 하지 않고도 1차원 배열에서 범위 내에 일정한 값을 더해주는 연산을 할 수 있는 방법이 있다.
이 문제의 풀이에서도 사용된 방법인데, 범위의 시작 위치와 종료 위치만 표시한 뒤
마지막에 한번만 누적합 계산해서 구하는 방법이다.
간단히 설명하면 아래와 같다.
왼쪽은 매 연산마다 반복문을 순회하면서 직접 값을 더해주는 방법이고,
오른쪽은 각 연산의 시작위치에는 값을 더해주고, 끝 위치에는 부호를 바꾼 값을 더해준뒤 마지막에 누적합을 통해 계산하는 과정이다.
두 과정의 결과가 같은 것을 확인할 수 있다.
따라서 배열 A를 구하기 위해서도 위와 같은 방식을 이용할 수 있다.
logs를 순회하면서 시작 시간과 종료 시간을 이용해서 조건에 맞는 값을 더해주면 된다.
다만, 현재 상황에서 더해주는 값은 '시청 기록의 수'이며,
하나의 로그는 곧 하나의 시청 기록이기 때문에 더해주는 값은 항상 1로 일정하다.
5. 구현
1. 시간초, 시청 기록 수 계산하기
adv_sec = time_to_sec(adv_time)
play_sec = time_to_sec(play_time)
sec = [0] * (play_sec+1)3개의 변수를 추가로 선언했다.
- adv_sec : adv_time을 초로 변환한 값
- play_sec : play_time을 초로 변환한 값
그리고 sec은 과정을 거치며 위에서 설명한 배열 A의 역할, 배열 T의 역할을 하게 될 것이다.
sec = [0] * (play_num+1)
for i in range(len(logs)):
s, e = map(time_to_sec, logs[i].split('-'))
sec[s] += 1
sec[e] -= 1logs를 순회하며 time_to_sec() 함수를 이용해 초 단위로 변환한다.
현재의 sec[] 배열은 위 설명에서 배열 A의 역할을 한다.
sec[x] = x 시각에 시작된 재생 구간의 개수 – x 시각에 종료된 재생구간의 개수
변환된 시작시간(s), 종료시간(e)을 이용해서
sec[시작시간] ~ sec[종료시간] 범위에 시청 기록의 수를 표시해야 하기 때문에
sec[시작시간]에는 1을 더해주고,
sec[종료시간]에는 -1을 더해준다.
2. 누적합을 계산해서 각 시간(초)의 시청 기록 수 저장하기
위에서 시작시간과 종료시간만 표시해주었던 것을
누적합을 통해 각 시간의 시청 기록의 수를 표시하도록 한다.
for i in range(1, len(sec)):
sec[i] += sec[i-1]이 연산을 거치면 sec[]는 다음과 같이 정의할 수 있다.
sec[x] = x초~x+1초의 시청 기록의 수
3. 다시한번 누적합을 계산해서, 시청 기록의 누적합을 구하기
이제 계산된 시청기록의 누적합을 계산해야한다.
for i in range(1, len(sec)):
sec[i] += sec[i-1]이제 sec[]의 정의는 아래와 같다
sec[x] = 0부터 x+1까지 x+1초 간의 구간을 포함하는 누적 재생시간
4. 최대 구간합을 갖는 광고 시작 시간 구하기
이제 구간합의 최대값을 구하며,
최대값이 마지막으로 갱신될 때의 i-adv_sec+1 초를
조건에 맞는 시간으로 변환해서 반환하면 된다.
max_time = 0
for i in range(adv_sec-1, play_sec):
if i >= adv_sec:
time = sec[i] - sec[i-adv_sec]
else:
time = sec[i]
if max_time < time:
max_time = time
answer = i-adv_sec+1초를 시간으로 바꾸는 함수도 따로 작성해주었다.
def sec_to_time(num:int):
h = f'{num//3600:02d}'
m = f'{(num%3600)//60:02d}'
s = f'{(num%3600)%60:02d}'
return ':'.join([h, m, s])코드
def solution(play_time, adv_time, logs):
answer = 0
adv_sec = time_to_sec(adv_time)
play_sec = time_to_sec(play_time)
sec = [0] * (play_sec+1)
for i in range(len(logs)):
s, e = map(time_to_sec, logs[i].split('-'))
sec[s] += 1
sec[e] -= 1
for i in range(1, len(sec)):
sec[i] += sec[i-1]
for i in range(1, len(sec)):
sec[i] += sec[i-1]
max_time = 0
for i in range(adv_sec-1, play_sec):
if i >= adv_sec:
time = sec[i] - sec[i-adv_sec]
else:
time = sec[i]
if max_time < time:
max_time = time
answer = i-adv_sec+1
return sec_to_time(answer)
def time_to_sec(time:str):
h, m, s = map(int, time.split(':'))
return s + m*60 + h*3600
def sec_to_time(num:int):
h = f'{num//3600:02d}'
m = f'{(num%3600)//60:02d}'
s = f'{(num%3600)%60:02d}'
return ':'.join([h, m , s])-
처음에는 활동 선택 문제와 유사한 형태(?)로 보여서 비슷한 접근 방식을 여러차례 시도해보았는데 방법이 떠오르지 않았다.
그 이후에, 연속된 일정 범위(광고 시간)값의 합을 구하는 문제이므로
특정 영역에 몇개의 시청 기록에 존재한다는것만 알 수 있으면 슬라이딩 윈도우로 풀 수 있지 않을까 했는데
이 '영역' 의 구분을 초단위로 하려는 생각은 하지 못했다.
문제를 유형화 하는 과정에서 사고가 닫히면 안된다는 생각이 들었다.
가능한 것과 불가능한 것의 경계를 정확히 알아야 하겠다.
