본문 바로가기
알고리즘 문제/Leetcode

[leetcode][933] Number of Recent Calls

by 햄과함께 2018. 11. 9.
반응형

문제 : https://leetcode.com/problems/number-of-recent-calls




조건에 t는 점점 커진다고 적혀있다.

따라서 한 번 범위에 포함되지 않는 핑은 앞으로도 계속 포함되지 않을 것이다.

최소 범위는 t - 3000인데 t가 계속 커질 것이므로 t-3000도 계속 커질 것임.

따라서 한 번 ping < t - 3000 가 된 ping은 앞으로도 최소 범위 t -3000 이전 값이 된다.


큐를 이용한다.

ping 함수에서 받는 t를 큐에 저장한다.

큐의 앞에서부터 t - 3000 보다 작은 것은 제외 시킨다. 다 제외 시켰을 때 큐의 크기를 반환시킨다.


시간복잡도는 O(N) 일 듯. N은 입력에서 받는 ping 함수 개수.




소스코드 : https://gist.github.com/fpdjsns/40262372506889ff5cfdfc8e6e8826a5

반응형

태그

댓글0