72414

날짜: 2022년 6월 1일 오후 9:38

오답: o

코드

Algorithm/72414.py at main · Junroot/Algorithm

풀이

틀린 풀이

시간이 최대 99시간 59분 59초로 360000초 까지 밖에 없다는 것을 인지했지만, 모든 로그를 360000크기의 배열에 값을 더해주는 것은 360000 * 300000 라는 시간복잡도가 발생할 것으로 보여 이 방법을 사용하지 않았다.

그래서 처음에는 로그들을 시작시간으로 정렬하여 시작 시간마다 누적 재생시간을 계산했는데 이 방법은 누적 재생시간을 매번 새로 계산해야돼서 시간 초과가 발생헀다.

맞는 풀이

결국 다른 사람 풀이를 봤는데, 처음에 언급한 방법을 활용하는 것이었다. 모든 로그들을 시작 시간과 종료 시간 두 배열로 나눠서 정렬하고, 360000크기의 배열을 돌면서 해당 시간에 시작하는 사람이 있으면 +1, 끝나는 사람이 있으면 -1을 해주면서 앞의 배열에서 누적시켜주면 된다. 이렇게 하면 360000 + 300000 라는 시간복잡도가 발생하므로 시간 초과가 발생하지 않는다.

참고 자료

https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/#문제-5-광고-삽입