[Leetcode] RecentCounter 문제
- RecentCounter() Initializes the counter with zero recent requests.
- int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].
- 1 9
- Each test case will call ping with strictly increasing values of t.
- At most 104 calls will be made to ping.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class RecentCounter:
def __init__(self):
self.pings = []
def ping(self, t: int) -> int:
self.pings.append(t)
count = 0
for i in range(len(self.pings)):
if self.pings[i] >= t-3000:
count += 1
return count
# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)
통과하지만 제출하니 시간초과.
그래서 뒤부터 세기로 하면 시간초과에 걸리지 않는다. 다음과 같이 수정.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class RecentCounter:
def __init__(self):
self.pings = []
def ping(self, t: int) -> int:
self.pings.append(t)
count = 0
for i in range(len(self.pings)-1, -1, -1):
if self.pings[i] >= t-3000:
count += 1
else:
break
return count
# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)
여기서 역방향 for문을 돌리기 위해
for i in range(len(self.pings)-1, -1, -1):
를 썼다.
for ping in reversed(self.pings):
를 쓸 수도 있지만, reversed() 함수 호출은 비용이 있다.
역방향 for문에 익숙해지자.
그리고 그 외에 무슨 풀이 방법들이 있는지 정리해보자.
pings 리스트를 만들고 start 포인트를 정한다. ping이 들어오면 pings리스트에 담고 start포인터가 유효범위안에 도달할 때까지 증가시킨다. 유효범위는 pings[start] >= t-3000 일 때다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class RecentCounter:
def __init__(self):
self.pings = []
self.start = 0 # 유효한 범위의 시작 인덱스
def ping(self, t: int) -> int:
self.pings.append(t)
# start 포인터를 유효한 범위까지 이동
while self.start = t - 3000:
break
self.start += 1
return len(self.pings) - self.start
내 원래 방법에서 주기적으로 pings리스트를 줄여서 정리해주는 로직만 추가함. 예를 들어 10000개가 쌓이면 [p for p in self.pings if p >= t-3000] 으로 리스트를 t-3000 이상인 값들로만 재정의한다.
이로써 메모리 사용량을 제한할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class RecentCounter:
def __init__(self):
self.pings = []
def ping(self, t: int) -> int:
self.pings.append(t)
# 배열이 너무 커지면 정리 (예: 10000개 초과시)
if len(self.pings) > 10000:
self.pings = [p for p in self.pings if p >= t - 3000]
# 유효한 ping 개수 세기 + 역순
count = 0
for i in range(len(self.pings)-1, -1, -1):
if self.pings[i] >= t - 3000:
count += 1
else:
break # 더 이상 유효한 ping 없음
return count
이 방식도 괜찮다. 그런데 pop(0)은 매번 배열을 이동해줘야 해서 N곱 만큼 시간복잡도가 늘어난다. O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class RecentCounter:
def __init__(self):
self.pings = []
def ping(self, t: int) -> int:
self.pings.append(t)
# 앞에서부터 오래된 ping들 제거
while self.pings:
if self.pings[0] >= t - 3000:
break
self.pings.pop(0) # 첫 번째 원소 제거
return len(self.pings)
그래서 python에는 deque 라이브러리가 있다.
from collections import deque로 가져오고 pings리스트를 deque()로 생성하고 pings.popleft() 로 왼쪽 ping을 제거해주면 된다. deque는 양쪽 끝 삽입/삭제가 O(1) 로 비용이 들지 않는다. 하지만 list와는 다르게 슬라이싱이 간단하게는 안되므로, 사용을 고려할 시 주의가 필요.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
from collections import deque
class RecentCounter:
def __init__(self):
self.pings = deque()
def ping(self, t: int) -> int:
self.pings.append(t)
# 3000ms 이전의 ping들을 제거
while self.pings and self.pings[0] < t - 3000:
self.pings.popleft()
return len(self.pings)
| 방식 | 시간복잡도 | 메모리 사용량 | 특징 |
|---|---|---|---|
| 원래 코드 | O(n) 매번 | 계속 증가 | 매번 전체 순회 |
| 역순 순회 | O(유효한 ping 수) | 계속 증가 | 뒤에서부터 카운트 |
| 투포인터 | O(1) amortized | 계속 증가 | start 포인터 사용 |
| 주기적 정리 | O(n) 때때로 | 제한적 | 임계값 도달시 정리 |
| 주기적 정리 + 역순 | O(유효한 ping 수) | 제한적 | 두 최적화 결합 |
| list.pop(0) | O(n²) | 제한적 | 실시간 정리 |
| deque | O(1) amortized | 최소한 | 실시간 정리 |
추천은, 특별한 라이브러리 제한이 없다면 deque를 쓰고,
제한이 있다면 투포인터 방법을 쓴다.
그런데 deque 사용법에 익숙하지 않다면 왠만하면 투포인터 + 주기적 정리(정리하면서 포인터도 재조정 해주는) 를 하면 메모리도 제한할 수 있으면서 투포인터의 장점을 누릴 수 있지 않을까.
다음처럼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class RecentCounter:
def __init__(self):
self.pings = []
self.start = 0
def ping(self, t: int) -> int:
self.pings.append(t)
# 배열이 너무 커지면 정리
if len(self.pings) > 10000:
# start 이후 부분만 유지하고 start 리셋
self.pings = self.pings[self.start:]
self.start = 0
# start 포인터를 유효한 범위까지 이동
while self.start = t - 3000:
break
self.start += 1
return len(self.pings) - self.start
- 카운트 리턴
- 투포인터 후 윈도우 사이즈 리턴