ABC 335 C번 복기 - 놓치기 쉬운 deque를 사용할 때 주의할 점(deque indexing is O(N)) + 배열과 연결리스트 접근 시간복잡도 차이

1. 문제

 

C - Loong Tracking (atcoder.jp)

C - Loong Tracking

 

 

2. 풀이

 

1번부터 N번까지 좌표가 있고, 1번 좌표는 쿼리에 의해 움직이게 된다.

 

1번 좌표가 움직이면, 2번,3번,4번,...,N번 좌표는 각각 1번,2번,3번,...,N-1번 좌표가 된다.

 

쿼리가 20만개이고 좌표수도 최대 100만개라 단순하게 접근하면 시간초과를 받을 것인데

 

그림으로 생각해보면 접근법을 생각할 수 있다

 

처음에 배열에 1번부터 N번까지 좌표가 있는데, 먼저 1번을 이동시키는 쿼리를 수행한다면..

 

1번 좌표를 빼서 이동시킨 좌표로 만들고..

 

[1,2,3,..,N] >>> [2,3,...,N]

 

1번 좌표 빼면 자연스럽게 이전에 2번,3번,N번 인덱스인 원소들이 1번,2번,..,N-1번 인덱스가 된다.

 

 

 

 

 

 

근데 1번을 어떤 좌표로 이동시킨 다음 이 좌표가 다시 1번이 되어야하는데,...

 

[2,3,4,..,N]에서 1번을 앞에 다시 넣어봤자.. 그냥 원래대로 [1,2,3,..,N]이 된다.

 

여기서 핵심은 N번 좌표는 더 이상 필요 없다는게 중요하다.

 

1번이 이동하면 이동 후에 이전의 N번은 더 이상 없어진다는 것

 

 

 

이러한 관찰에 입각해서, deque를 이용해서 먼저 [(1,0),...,(N,0)]으로 초기 좌표들을 초기화해두고..

 

항상 head의 좌표는 h_x = 1, h_y = 0으로 추적해둔다.

 

배열 head = [1,0]으로 만들면 배열의 원소를 변경시킬경우 deque에 넣은 원소도 바뀔 위험이 있으니..

 

좌표로 만들어두고

 

매 쿼리마다 head를 이동시키는 쿼리를 수행할 때는, head를 이동시키고..

 

이동시킨 좌표를 왼쪽에 넣어두면

 

[(h_x,h_y),(1,0),....,(N,0)]이고 마지막 좌표 (N,0)을 없애면 [(h_x,h_y),(1,0),(2,0),...,(N-1,0)]으로

 

이전 1번 좌표 (1,0)은 (h_x,h_y)

 

이전 2번 좌표 (2,0)은 (1,0)

 

이전 3번 좌표 (3,0)은 (2,0)

 

...

 

이전 N번 좌표 (N,0)은 (N-1,0)이 된다.

 

이렇게 하면 1번 좌표만 움직여서 모든 좌표를 O(1)에 이동시킬 수 있게 된다.

 

그러면 이제 현재 좌표들이 항상 준비되어 있으니 i번째 part의 좌표를 구할 때는 그냥 인덱싱으로 구하면 될 것이다

 

from collections import deque
from sys import stdin

n,q = map(int,stdin.readline().split())

h_x = 1
h_y = 0

path = deque()

for i in range(1,n+1):
    
    path.append((i,0))

delta = {'R':[1,0], 'L':[-1,0], 'U':[0,1], 'D':[0,-1]}

for _ in range(q):
    
    a,b = stdin.readline().rstrip().split()

    if a == '1':
        
        h_x += delta[b][0]
        h_y += delta[b][1]

        path.appendleft((h_x,h_y))
        path.pop()

    else:
        
        print(*path[int(b)-1])

 

 

근데 완벽하게 O(N+Q)에 해결했다고 생각했는데 온몸비틀기를 했는데 시간초과나더라고

 

그러다보니 리스트를 이용해서 굳이 pop하지말고.. 뒤쪽에 계속 append하면 된다는걸 알았다

 

처음에 이렇게 [N,N-1,N-2,...,3,2,1] 역으로 배열을 배치해두고....

 

 

 

그리고 1번 좌표를 이동시키는 쿼리를 수행할때마다, 가지고 있는 head 좌표를 이용해서 이동시킨 다음,

 

그냥 리스트의 마지막에 append시키기만 한다면...

 

그림과 같이 이전에 2번 인덱스였던 좌표 (2,0)이 1번 인덱스였던 (1,0)으로 이동했고

 

n번 인덱스였던 (N,0)이 (N-1,0)으로 이동한 모습을 볼 수 있다.

 

그리고 굳이 (N,0)은 제거하지 않아도 된다.

 

어차피 i번째 part의 좌표를 찾는 쿼리는 1번부터 N번중 하나를 찾는거니까 메모리가 허용하는한 

 

그냥 둬도 된다는 소리

 

 

 

 

from sys import stdin

n,q = map(int,stdin.readline().split())

h_x = 1
h_y = 0

path = [(i,0) for i in range(n,0,-1)]

delta = {'R':[1,0], 'L':[-1,0], 'U':[0,1], 'D':[0,-1]}

for _ in range(q):
    
    a,b = stdin.readline().rstrip().split()

    if a == '1':
        
        h_x += delta[b][0]
        h_y += delta[b][1]

        path.append((h_x,h_y))

    else:
        
        b = int(b)
        
        print(*path[-b])

 

 

이러면 시간초과를 안받는데, 분명 deque()도 마지막 원소를 pop()하고 왼쪽에 append()하면 전부 O(1)인데..

 

q가 최대 20만이라 O(20만)이나 O(40만)이나 시간차이가 없는데

 

왜 deque로 했더니 시간초과가 나는가.. 이제 여기가 고민된거

 

그래서 그냥 똑같이 deque()로만 바꿔봄

 

from collections import deque

from sys import stdin

n,q = map(int,stdin.readline().split())

h_x = 1
h_y = 0

path = deque()

for i in range(n,0,-1):
    
    path.append((i,0))
    
delta = {'R':[1,0], 'L':[-1,0], 'U':[0,1], 'D':[0,-1]}

for _ in range(q):
    
    a,b = stdin.readline().rstrip().split()

    if a == '1':
        
        h_x += delta[b][0]
        h_y += delta[b][1]

        path.append((h_x,h_y))

    else:
        
        b = int(b)
        
        print(*path[-b])

 

 

그랬더니 여전히 시간초과나더라...

 

문득 들었던 생각이 deque가 예전에는 인덱싱이 안되던것 같은데 갑자기 되는게 이상하더라고

 

 

 

근데 알고보니 deque는 인덱싱이 O(N)이더라

 

 

 

그래서 의외로 인덱싱에 접근하는 연산이 O(N)이다보니 시간초과나는거더라고

 

이는 python의 deque가 이중연결리스트라서 그렇다

 

연결리스트들은 n번째 원소에 접근할려면 1번 node부터 node를 따라 next로 이동해서, n번까지 이동하니까

 

보통 O(N)이다

 

https://velog.io/@mindol/%ED%8C%8C%EC%9D%B4%EC%8D%AC-deque%EC%9D%98-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%EC%A0%91%EA%B7%BC-%EC%97%B0%EC%82%B0-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

[Python] deque의 접근 연산 시간 복잡도

 

https://hyeinisfree.tistory.com/64

[Data Structure] 연결 리스트(Linked List)

 

 

그러면 여기서 궁금한건 list는 어떻게 인덱싱이 O(1)인지 궁금하겠지

 

배열은 모든 원소의 메모리 주소를 알고 있기 때문에 원하는 index i의 원소는 단순 산수로 계산할 수 있다고 한다

 

그래서 배열은 임의접근이 가능하다

 

https://www.geeksforgeeks.org/why-does-accessing-an-array-element-take-o1-time/

Why does accessing an Array element take O(1) time? - GeeksforGeeks

 

https://post.naver.com/viewer/postView.nhn?volumeNo=7509471&memberNo=25379965

자료 구조의 기본, 배열과 연결리스트 쉽게 이해하기