[항해99]알고리즘_05

[Python] 백준 1021 회전하는 큐

   문제분석   

# 파이썬은 collections모듈의 deque(double-ended queue)을 통해 큐 자료구조 구현

# 큐는 선입선출 방식이지만 덱은 양방향에서 삽입과 삭제 가능
# 그럼 그냥 리스트를 쓰면 되지?

  -> 리스트는 배열의 형태이기 때문에 index 의 앞 부분에서 삽입과 삭제가 일어나면

      삭제된 곳을 채우기 위해 그 뒤 엘리먼트들이 앞으로 모두 움직이면서 시간복잡도가 O(n)

      시간복잡도 참고  https://wiki.python.org/moin/TimeComplexity

      Deque 메소드 참고  https://docs.python.org/3/library/collections.html#collections.deque

  -> 덱은 데이터 추가 삭제 시 O(1)

# import 해서 사용

 

   예시첨부   

# 10 3  ->  큐의 크기 n, 뽑아내려는 수의 개수 m
# 2 9 5  ->  뽑아내려는 수의 위치

n, m = 10, 3

# 위치만 필요하지 값은 상관없으니 편의상 위치와 값을 같게 설정했다.
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# 위치2 뽑기 -> 뽑을 위치 2가 n개 중에서 전반에 위치하므로 2번 수행
1. 2번 수행    [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]
2. 1번 수행    [3, 4, 5, 6, 7, 8, 9, 10, 1]

# 위치9 뽑기 -> 뽑을 위치 9가 n개 중에서 후반에 위치하므로 3번 수행
3. 3번 수행    [1, 3, 4, 5, 6, 7, 8, 9, 10]
   3번 수행    [10, 1, 3, 4, 5, 6, 7, 8, 9]
   3번 수행    [9, 10, 1, 3, 4, 5, 6, 7, 8]
4. 1번 수행    [10, 1, 3, 4, 5, 6, 7, 8]

# 위치5 뽑기 -> 뽑을 위치 5가 n개 중에서 후반에 위치하므로 3번 수행
5. 3번 수행    [8, 10, 1, 3, 4, 5, 6, 7]
   3번 수행    [7, 8, 10, 1, 3, 4, 5, 6]
   3번 수행    [6, 7, 8, 10, 1, 3, 4, 5]
   3번 수행    [5, 6, 7, 8, 10, 1, 3, 4]
6. 1번 수행    [6, 7, 8, 10, 1, 3, 4]

위 과정을 정리하자면,

① n개를 리스트로 입력 받는다.

② 입력받은 리스트 길이를 반으로 나눠 뽑아야하는 수의 위치와 비교하여 작다면 2번(왼쪽으로 한칸 이동)

③ 입력받은 리스트 길이를 반으로 나눠 뽑아야하는 수의 위치와 비교하여 크다면 3번(오른쪽으로 한칸 이동)

④ 2,3번 수행할때마다 횟수 세기.

⑤ 뽑을 수가 제일 앞으로 오면 1번 수행.

 

 

   문제풀이   

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())    # 큐의 크기 n과 뽑아내려고 하는 수의 개수 m을 입력값으로 받기
position = list(map(int, input().split()))  # 뽑아내려는 수의 위치를 입력값으로 받기
dq = deque([i for i in range(1, n+1)])  # deque([1, 2, 3,...,n])
# dq = deque()
# for i in range(1, n+1):
#     dq.append(i)

count = 0   # 2, 3번 수행하면 카운트 올리기
for i in position:  # 뽑아내려는 수의 위치 하나씩 반복문 돌리기
    while True:     # 뽑을 때까지 계속 돌리기
        if dq[0] == i:  # dq의 첫인덱스가 뽑아내려는 수의 위치와 같다면 1번 수행
            dq.popleft()
            break
        else:
            if dq.index(i) < len(dq)/2:  # 뽑아내려는 수의 위치 인덱스가 dq의 길이를 반으로 나눈것보다 작을때는 왼쪽으로 움직여야 최소
                while dq[0] != i:   # dq의 첫번째 인덱스가 i와 같아질때까지 반복
                    dq.append(dq.popleft())  # 파이썬 첨부자료 확인
                    count += 1
            else:   # 뽑아내려는 수의 위치 인덱스가 dq의 길이를 반으로 나눈것보다 클때는 오른쪽으로 움직여야 최소
                while dq[0] != i:
                    dq.appendleft(dq.pop())  # 파이썬 첨부자료 확인
                    count += 1
print(count)

 

출처 https://docs.python.org/ko/3/library/collections.html?highlight=deque#collections.deque