(BOJ) 1021. 회전하는 큐

문제 설명

💡 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.
지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., a10이었던 것이 a2, ..., a10와 같이 된다.

2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., a1가 a2, ..., a10, a9이 된다.

3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., a10가 a10, a1, ..., a9이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

문제 풀이 IDEA

• 1번 함수는 pop을 사용.
• 2번 함수는 popleft를 사용한 후에 다시 append를 사용.
• 3번 함수는 pop을 해서 appendleft를 사용.

결국 문제는 첫번째에 있는걸 뒤로 돌릴거냐 뒤에있는걸 앞으로 돌릴거냐의 문제!

첫번째 IDEA

|맨앞의 수- 빼야할 수| vs |맨뒤의 수 - 빼야할 수|

→ 괜찮을 줄 알았지만 앞의 수가 뒤로 갈 경우 절댓값의 비교로 불가능

from collections import deque

N,M=map(int,input().split())

array=deque([i+1 for i in range(N)])
output=list(map(int,input().split()))

count=0
for i in output:
    if abs(array[0]-i)<abs(array[-1]-i):
        while array[0]!=i:
            array.append(array.popleft())
            count+=1
    else:
         while array[0]!=i:
            array.appendleft(array.pop())
            count+=1
    array.popleft()
    print(count)

print(count)

-실패

두번째 IDEA

빼야할 수의 index가 중간보다 앞인지 뒤인지를 파악해서 2,3번 함수를 사용

from collections import deque

N,M=map(int,input().split())

array=deque([i+1 for i in range(N)])
output=list(map(int,input().split()))

count=0
for i in output:
    **if array.index(i)<=(len(array)//2):# 만약 중간보다 앞일경우**
        while array[0]!=i: # 2번 함수 진행
            array.append(array.popleft())
            count+=1 # 2번 함수 사용횟수 +1
    else: # 3번 함수 사용 횟수
         while array[0]!=i:
            array.appendleft(array.pop())
            count+=1
    array.popleft()

print(count) # 사용횟수 출력

메모리 34104KB, 시간 64ms