회전하는 큐

1부터 N까지 차례로 나열된 원소 중에서 두번째 줄에 입력 받은 숫자를 규칙에 따라 뽑을 때 큐를 왼쪽 혹은 오른쪽으로 이동시킨 횟수를 구하는 문제다.

숫자를 꺼내기 위해 왼쪽(2번 연산)으로 이동시킬지 오른쪽(3번 연산)으로 이동시킬지 판단해야 한다. 리스트의 개수가 짝수일 때는 len(list)//2 번째 있는 요소를 첫 번째 원소로 위치시키는데 왼쪽이나 오른쪽이나 횟수가 같다. 리스트의 개수가 홀수일 때는 len(list)//2 번째 있는 요소를 첫 번째 원소로 위치시키는데 왼쪽으로 이동시키는 것이 더 적은 횟수를 소모한다. len(list)//2 번째 요소부터는 반대로 오른쪽으로 이동시키는 것이 더 적은 횟수를 소모한다.

왼쪽, 오른쪽으로 한칸 이동시키는 연산은 python에서 ‘덱’을 이용해 구현할 수 있다. List에서도 pop, insert와 append를 사용해 구현할 수 있지만, pop(0)와 insert(0,x)는 시간 복잡도가 O(N)으로 다루는 원소가 많아질수록 비효율적이다. 이것이 Collections의 deque를 사용하기로 한 이유이다. Reference - 시간복잡도

Number에 1부터 N까지의 숫자로 이루어진 리스트를 집어넣고, pick의 첫번째 값과 number의 첫번째 값이 일치할 때 까지 왼쪽 혹은 오른쪽으로 한 칸 이동시키는 연산을 수행하도록 했다. 연산을 수행할 때 마다 cnt에 횟수를 추가해 주었다.

Case 1 – deque

n,m= map(int,input().split())
pick=list(map(int,input().split()))
number=list(range(1,n+1))

from collections import deque
cnt=0
_pick=deque(pick)
_number=deque(number)

while _pick:
    a=_pick[0]
    while _number[0]!=a:
        idx=_number.index(a)
        if idx <= len(_number)//2:
            _number.append(_number.popleft())
        else:
            _number.appendleft(_number.pop())
        cnt+=1
    _number.popleft()
    _pick.popleft()
print(cnt)

Case 2 - list

list를 활용한 코드로 deque의 popleft, appendleft 대신 pop(0), insert()를 사용했다. 이 방법을 사용할 경우 시간복잡도가 증가할 수 있다.

n,m= map(int,input().split())
pick=list(map(int,input().split()))
number=list(range(1,n+1))

cnt=0

while pick:
    a=pick[0]
    while number[0]!=a:
        idx=number.index(a)
        if idx <= len(number)//2:
            number.append(number.pop(0))
        else:
            number.insert(0,number.pop())
        cnt+=1
    number.pop(0)
    pick.pop(0)
print(cnt)

코드 길이 460이 deque를 사용한 코드 그리고 368이 list를 사용한 코드이다. 예상과는 달리 list를 사용한 코드의 시간이 24ms 짧았다… (채점에 사용된 리스트의 크기가 충분히 길지 않아서 이런 일이 생긴듯 하다.)

[다시 풀어보기] ✔ - 2020.10.22