[백준] 1021 회전하는 큐 파이썬 풀이 (큐)

코드

from collections import deque


def move_left(queue):
    first = queue.popleft()
    queue.append(first)

def move_right(queue):
    last = queue.pop()
    queue.appendleft(last)

def find_index(queue, num):
    index = 0
    for index in range(len(queue)):
        if queue[index] == num:
            break
    return index

# --------------------------------------------
N,M = map(int, input().split())
queue = deque()
find_number = []
for i in range(N):
    queue.append(i+1)

find_number= list(map(int,input().split()))
# print(find_number)
# print(queue)
count = 0
for i in find_number:
    if queue[0] == i:
        queue.popleft()
        continue
    else:
        number_index = find_index(queue, i) #queue에서 찾을 숫자의 위치를 찾음
        if number_index < len(queue)/2:
            for i in range(number_index):
                move_left(queue)
                count+=1
            queue.popleft()
        else:
            for i in range(len(queue)- number_index):
                move_right(queue)
                count+=1
            queue.popleft()
print(count)

풀이

deque를 사용해서 함수를 만들어서 하란대로 했다.

left로 움직이는 것은

첫번째 원소를 빼서 뒤에 넣고

right로 움직이는 것은

마지막 원소를 빼서 맨 앞에 넣고

index를 찾는 함수는

큐를 돌면서 index를 찾았다.

그리고 주어진 숫자만큼 큐를 만들었고 [1,2,3,4,5,...] 이렇게

찾을 숫자들을 리스트로 만들었다

 

그리고 find_number을 돌면서 찾을 숫자가 어디있는지 찾고

그 숫자를 왼쪽으로 옮기면 이득일지 오른쪽으로 옮기면 이득일지 확인한 다음에

수행을 해주고 한 만큼 count를 1씩 올렸다.

 

---

다른 사람의 풀이

N,M = map(int,input().split(' '))
pop_num = list(map(int,input().split(' ')))
queue = list(range(1,N+1))
move = 0

for i in pop_num:
  current_index = queue.index(i)
  if current_index > len(queue)//2:
    move += (len(queue)- (current_index))
  else:
    move += current_index

  queue = queue[current_index+1:] + queue[:current_index]

print(move)

근데 저렇게 무식하게 안풀고 이렇게 풀어도 된다.

같은 스터디 조원분의 코드인데 천재인줄 알았다!!!!

찾을 숫자를 pop_num에 저장해놓고

for문을 돌면서 그 찾을 넘버가 지금 큐에 어디있는지 확인하고

오른쪽으로 움직이는 게 이득이면( 큐의 길이의 절반보다 오른쪽에 있으면)

len(queue)- 현재위치 만큼 move를 더해준다.

예를 들어 지금 큐의 길이가 9인데

현재위치가 7번째 인덱스이면 오른쪽으로 8번째 인덱스로 이동, 0번째 인덱스로 이동하여

총 2번 움직여야한다

그래서 길이 - 현재위치가 됨

 

왼쪽으로 움직이는게 이득이면(큐의 길이의 절반보다 왼쪽에 있으면)

move에 현재 인덱스를 더해준다

예를들어 지금 3번째 인덱스에 있으면 2번으로 이동, 1번으로 이동, 0번으로 이동->> 총 3번 이동해야하기 때문

 

숫자를 하나 빼고 나서는

큐를 재정의 해준다

1 2 3 4 5 6 7 8 9 에서

4를 빼면

4를 왼쪽으로 이동해서

4 5 6 7 8 9 1 2 3 을 만든다음

4를 빼고

5 6 7 8 9 1 2 3 이 되므로

4 뒤의 수부터 끝까지 + 처음부터 4바로 전까지 큐를 더해서 만들어준다.