[알고리즘] 백준 파이썬 1021 회전하는 큐 | 이해하기

 

 

 

 

 

 

https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐

 

 

🧐 문제 이해하기

 

만약 입력값이 다음과 같다면,

N(큐의 크기) = 32

M(뽑아 내려는 개수) = 6

뽑아내려는 위치의 값 = 27, 16, 30, 11 , 6 , 23 (그냥 이 숫자를 뺄건데 위치도 같이 겸한다 생각하면 편함)

 

원하는 위치에서 원하는 개수를 빼려고 연산하는데 얼마나 드는지 계산하는 것이 문제! (몇 번 연산을 해야하는 지)

 

로직 구성

 

입력값 받기

# deque 쓰기
from collections import deque

n,m=map(int,input().split()) # 큐의 크기, 뽑아낼 숫자 입력 받기
que=deque(range(1,n+1)) # 큐의 크기로 큐 만들기
pot_list=deque(map(int,input().split())) # 뽑아낼 값 리스트

# map : 두번째 인자의 값의 하나하나를 첫번째 인자의 값으로 바꿔준다.

 

입력값을 출력해본다면?

print (n,n) #32 6
print (que) #deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32])
print (pop_list) #deque([27, 16, 30, 11, 6, 23])

 

계산하기

 

방법 1

count = 0
for pop_num in pop_list:
    while pop_list: # 뽑아내려는 수의 위치를 각각 반복
        if que[0] == pop_num: # 맨 앞에 원하는 값이 오면 뽑아 버린다.
            que.popleft()
            break
        else: 
            if que.index(pop_num) <= len(que)//2: # 큐에서 뽑아내려는 수의 위치가 que 앞 부분에 있을 때
                que.rotate(-1) # 왼쪽으로 회전
                count += 1 
            else:
                que.rotate(1)
                count += 1

print(count)

count : 연산 횟수 카운트

while pop_list : 뽑아내려는 위치가 있을 때

 

로직 : 

맨 앞에 원하는 것이 있을 때는 뽑아 버린다.

 

만약 맨 앞에 원하는 것이 없다고 하자.

그렇다면 원하는 값이 앞 쪽에 있는지, 뒷 쪽에 있는지를 판단해서 뽑도록 해서 무조건 앞에서 뽑기보다는 카운트 수가 적게 해준다.

이 때 원하는 값이 앞에 위치해 있다면, 왼쪽으로 회전해서 왼쪽에 있는 걸 빨리 뽑아내도록 하고, 아니면 그 반대이다.

 

앞 부분 뒷 부분 판단은, que의 길이를 반으로 나눠서 앞 뒤를 검사하면 된다.

que의 길이를 반으로 나눈 것을 기준으로 하고, 그 검사값은 que의 원하는 숫자가 있는 위치(que.indexof(빼려는 위치))이다. 

* (que.indexof(빼려는 값(위치))) -> 만약 빼려는 값(위치)가 1이다? ->  que.indexof(1) que의 1번째, 첫번째 인덱스 넘버는 0 부터 시작하므로 que의 인덱스는 0.

그리고 큐의 길이를 10으로 해보자.

그러면, que의 인덱스(위치) 0(맨 앞에 있는 값)이 ,  큐의 길이 10의 반 5보다 큰지 작은지(앞에 있는지 뒤에 있는지) 검사해주는 것이다.

위치가 반 보다 앞에 있으면 앞에거 부터 빼줄 것이고, 뒤에 있으면 뒤 부터 빼 줄 것이다.

 

이런 식으로 해서 조건을 걸어주고, 회전을 할 때마다 연산을 하기 때문에 카운트를 올려주고, 맨 앞에 있으면 바로 뽑아주고 이렇게 반복하다가 다 뽑으면 출력해준다.

 

 

 

 

방법 2

count=0
while pop_list:
    mid=len(que)//2
    if que.index(pop_list[0])>mid: # 오른쪽 부분에 있다면 가져와서 앞에 붙임 (오른쪽 다음 거를 검사해야하니까)
        while pop_list[0]!=que[0]:
            que.appendleft(que.pop())  # 3번 연산 (오른쪽으로 한 칸이동)
            count+=1
        que.popleft()
        pop_list.popleft()
    else: # 왼쪽 부분에 있다면 왼쪽꺼 오른쪽에 갔다 붙임 (왼쪽 다음 거를 검사해야하니까)
        while pop_list[0]!=que[0]:
            que.append(que.popleft()) # 2번 연산 (왼쪽으로 한 칸 이동)
            count+=1
        que.popleft()
        pop_list.popleft()

print(count)

 

count : 연산 횟수 카운트

while pop_list : 뽑아내려는 위치가 있을 때

 

로직 : 위와 로직이 비슷하다. 다만, rotate 대신에 pop, append를 썼다는 것. 그리고 값을 뽑아 낸 다음에 뽑아낼 값 리스트에서도 뽑아주는 것. 그러면 그 리스트의 맨 앞 값이 다음 뽑아낼 값이 되므로 그걸 que의 위치로 해서 앞 쪽인지 뒤 쪽인지 비교해준다.

 

조금 더 자세히 설명:

맨 앞에 있는 거가 원하는 값이 아닐 때, 큐를 반으로 쪼개서 뒤가 가까우면 뒤에꺼 뽑아서 앞에다 붙힌다. (rotate 대신에 pop, append로 뽑아다 붙이는 거지만 똑같은 원리다.)

이 연산을 할 때마다 카운트 증가

그리고 원하는 값이 온다면 빼준다. 여기는 연산하는게 아니고 그냥 빼주는 거니까 카운트 증가 X

다만 여기는 뽑아낼 값을 뽑아낼 때마다 pop_list(뽑아낼 값  리스트)에서도 빼준다.

그리고 검사할 때도 그 리스트의 맨 앞 값으로 검사한다. 어차피 뽑아 냈으니 다음 거는 맨 앞일 것이다.

이런식의 위와 비슷한 로직이다. 

 

 

✍️ 전체 코드

방법1 

from collections import deque

n,m = map(int,input().split())
que = deque([i for i in range(1,n+1)]) # deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) n이 10이라면 이렇게 담긴다.
pop_list = list(map(int,input().split())) #뽑아내려고 하는 수의 위치(값) 리스트 m이 3이라면 [1, 2, 3]


count = 0
for pop_num in pop_list:
    while pop_list:
        if que[0] == pop_num:
            que.popleft()
            break
        else:
            if que.index(pop_num) <= len(que)//2:
                que.rotate(-1)
                count += 1
            else:
                que.rotate(1)
                count += 1

print(count)

 

방법2

from collections import deque
#map : 두번째 인자의 값의 하나하나를 첫번째 인자의 값으로 바꿔준다.

n,m=map(int,input().split())
que=deque(range(1,n+1))
pop_list=deque(map(int,input().split()))

count=0
while pop_list:
    mid=len(que)//2
    if que.index(pop_list[0])>mid:
        while pop_list[0]!=que[0]:
            que.appendleft(que.pop())
            count+=1
        que.popleft()
        pop_list.popleft()
    else:
        while pop_list[0]!=que[0]:
            que.append(que.popleft())
            count+=1
        que.popleft()
        pop_list.popleft()

print(count)

 

🧐 deque

 

✔︎ 양방향 큐(deque)에 대하여

deque(double-ended queue)란 무엇인가?

: 앞과 뒤에서 즉, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조를 의미

 

✔︎deque 쓰기

from collections import deque

 

✔︎ deque 메소드

#deque 메소드

deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.
deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.
deque.pop(): 데크의 오른쪽 끝 엘리먼트를 데크에서 삭제한다.
deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 데크에서 삭제한다.
deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.
deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.(왼쪽으로 확장, 왼쪽부터 큐에 하나씩 입력 -> 1,2,3이면 하나씩 넣어지면 3,2,1로 출력)
deque.remove(item): item을 데크에서 찾아 삭제한다.
deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).

https://docs.python.org/3/library/collections.html#collections.deque

collections — Container datatypes — Python 3.10.2 documentation