level3_광고삽입(2021 KAKAO BLIND RECRUITMENT).cpp

문제

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

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

---

접근방법

1) 접근 사고

문제를 다 읽고 정리하면 "광고의 누적시간을 구하세요"가 문제에서 제시하는 핵심이다. 처음에 어떻게 구현을 해야할 지 감이 안잡혔다. 완전탐색으로 구현을 하게 되면 범위 때문에 시간초과가 발생할 게 당연하였기 때문에 O(longN)이나 O(N)으로 해결하는 알고리즘들을 생각하였다. 그 중 누적값을 사용하여 투 포인터로 해결하면 광고의 누적시간을 구간합을 사용하여 구할 수 있을거 같아서 이쪽으로 구현하였다.

 

2) 시간 복잡도

O(n)

 

3) 실수

투 포인터의 구현과정에서 광고의 시작시간의 끝 부터 시작하므로 광고시작시간을 빼주고 1을 더해줘야하는데 이러한 과정없이 진행하여 논리오류가 발생함

 

4) PS

 

---

정답 코드