알고리즘/programmers

[Programmers] 광고 삽입

꾸준함. 2022. 7. 21. 00:53

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/72414#

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

슬라이딩 윈도우 기법을 이용하는 문제였습니다.

시스템 케이스 17번에서 거의 10초가 걸렸기 때문에 아슬아슬하게 통과한 코드입니다.

 

알고리즘은 아래와 같습니다.

1. 입출력 예 #2를 보면 01:00:00-11:00:00 : 해당 구간이 1회(2번 기록) 재생되었으므로 누적 재생시간은 10시간 00분 00초라고 주어집니다. 따라서, 주어진 광고의 범위는 사실상 [시작 시간 + 1초, 종료 시간]입니다.

2. 이 점을 유의하여 logs 벡터를 전 처리하여 arr 배열에 각 초마다 몇 개의 프로그램이 동시에 진행되고 있는지 기록합니다.

3. 슬라이딩 윈도우를 진행할 때 광고 삽입 시간을 업데이트하는 기준이 필요하므로 우선, [0초, ad_time초] 구간에서 광고가 총 몇 초동안 상영이 되는지 기록하고 answer를 "00:00:00"초로 지정합니다.

4. 1초씩 슬라이딩하면서 총 광고 상영시간을 체크하고 광고가 기존에 기록한 시간보다 더 오래 상영되었다면 answer를 업데이트합니다. (주의: 정답이 여러 개라면 가장 빠른 시간을 반환해야 하므로 반드시 기존에 기록한 시간보다 초과할 때만 업데이트합니다. 동등할 경우 업데이트 X)

5. 4번에서 구한 asnwer를 반환합니다.

 

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~

반응형