Table of contents
들어가며
걸린 시간: 33분
문제 조건을 보면, 쿼리의 개수인 N은 최대 50만이고, 각 쿼리 당 탐색을 해야 하는 리스트의 최대 길이는 30만입니다.
그래서 하나의 쿼리에서의 탐색 시간복잡도를 Order of Log P로 최적화하는 것을 의심했습니다.
접근
예시 input들을 직접 손으로 그려 가면서 구현 방법에 대해 접근을 했습니다.
(posI, posJ)로 입력 받은 쿼리에서,board[posI][posJ]에 이미 손가락이 올려져 있는지 확인한다. (코드에서는 이를 cacheHit라고 했습니다.)- 만약 cache hit가 되지 않았다면, 손가락을 하나 올려야 되기 때문에, 움직임을 +1 해준다.
- 그리고 지금 실행하려는 쿼리의 posJ보다 큰 값이
board[posI]리스트에 있는지 확인해서, 있다면 그 원소들을 pop해준다. (손가락을 떼준다.) - 떼어낸 손가락 개수만큼 움직임을 플러스해준다.
구현
import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
if __name__ == "__main__":
ans = 0
N, P = map(int, input().strip().split())
board = [[] for _ in range(7)]
for _ in range(N):
posI, posJ = map(int, input().strip().split())
# print(f"query nums: {posI}, {posJ}")
updateAns = 0
cacheHit = False
rightInsertPos = bisect_right(board[posI], posJ)
# print(f"right insert pos: {rightInsertPos}")
leftInsertPos = bisect_left(board[posI], posJ)
# print(f"left insert pos: {leftInsertPos}")
numPosJ = rightInsertPos - leftInsertPos
# check cache hit
if numPosJ == 0:
# no cache hit, caching!
updateAns += 1
else:
# cache hit!
cacheHit = True
# check if higher j pos exists
if len(board[posI]) > rightInsertPos:
# pop elements that are bigger than query j pos
while board[posI] and board[posI][-1] > posJ:
board[posI].pop()
updateAns += 1
if not cacheHit:
board[posI].append(posJ)
# print(board[posI])
ans += updateAns
print(ans)여기서 손가락이 올려져 있는지 확인 그리고 posJ보다 큰 값이 있는지 확인 이 두 작업은 당연히 bisect_left, bisect_right 라이브러리를 이용해서 order of Log P 시간 복잡도에 해결이 되게 했습니다.