[백준 1021번] 회전하는 큐

www.acmicpc.net/problem/1021

1021번: 회전하는 큐

난이도: 

중상

 

알고리즘 분류:

자료구조, 덱

 

# 백준 1021번 (회전하는 큐)

# 문제 이해
# 10 3          큐의 크기 10(n). 뽑아내려는 수의 개수 3(m).
# 2 9 5         뽑아내려는 숫자: 2, 9, 5

# list가 비어있으면 False인 것을 잘 활용하자.


# 큐를 왼쪽으로 돌릴지, 오른쪽으로 돌릴지 함수 짜놓기
def move_left(que, count):          # que = [1,2,3,4,5,6,7,8,9,10] <- 2를 뽑자
    count = count + 1               # 1번 이동
    delete_head = que.pop(0)        # que = [2,3,4,5,6,7,8,9,10]
    que.append(delete_head)         # que = [2,3,4,5,6,7,8,9,10,1]
    return que, count               # que = [2,3,4,5,6,7,8,9,10,1], count = 1

def move_right(que, count):
    count = count + 1               # que = [1,2,3,4,5,6,7,8,9,10] <- 9를 뽑자
    delete_head = [que.pop()]       # delete_head = [10], que = [1,2,3,4,5,6,7,8,9]
    que = delete_head + que         # que = [10,1,2,3,4,5,6,7,8,9]  / 파이썬 콘솔 돌리니까 이렇게 나옴.
    return que, count               # 이걸 count=2번 하면, que = [9,10,1,2,3,4,5,6,7,8]



n, m = map(int, input().split())                        # 10, 3
output_nums_list = list(map(int, input().split()))      # 2, 9, 5

# 큐를 만들어 놓자.
que = list(range(1, n+1))               # que = [1,2,3,4,5,6,7,8,9,10]
count = 0                               # 몇번 옮겼는지 세야 하니까

while output_nums_list:                 # [2, 9, 5] -> 2를 뽑자.   // 리스트를 다 뽑고 나면 output_nums_list=[]가 되는데 ==False!
    if que[0] == output_nums_list[0]:   # que = [2,3,4,5,6,7,8,9,10,1], count = 1
        que.pop(0)                      # 2, que = [3,4,5,6,7,8,9,10,1]
        output_nums_list.pop(0)         # 2, output_nums_list = [9, 5]
    else:                               # que = [1,2,3,4,'5',6,7,8,9,10]
        if que.index(output_nums_list[0]) <= len(que) // 2:     # 3 <= 5    (5보다 왼쪽에 있으니까 왼쪽으로 돌리자)
            while que[0] != output_nums_list[0]:                # 1 != 2 == True
                que, count = move_left(que, count)
        else:                           #que.index(output_nums_list[0]) > len(que) // 2:
            while que[0] != output_nums_list[0]:
                que, count = move_right(que, count)

print(count)

 

이 문제는 이해하기가 힘들었다. '큐'라는 개념을 알고 접해야 할 것 같아서 pdf 보고, 강의 보고 하니 개념은 알 것 같은데, 코드로 어떻게 옮길지가...

모듈? 써서 푸는 방법 말고, 오른쪽/왼쪽으로 옮기는 함수 써서 풀고 싶었는데 구글링해서 찾았다.

점점 나아지는 것 같긴 한데, 아직 미미한 수준이다. 항해99 끝나는 날까지 알고리즘 문제는 하루에 적어도 1시간은 쓸 테니까 꾸준히 하자.

 

# 수정 1.1

collections 모듈 deque라는 것을 이용하면, 쉽게 코드를 짤 수 있다.팀원분이 deque 설명이 나와있는 링크를 보내주셔서 읽어보고 구글링 더 해서 공부하고 왔는데, deque가 오늘 강의에서 배운 queue의 dequeue인 줄 알고 그냥 넘겼는데 아니었다.deque 중에서 rotate랑 extend 함수가 흥미로웠다. (append vs extend)

 

1) dongdongfather.tistory.com/72

[파이썬 기초] 스택과 큐의 기능을 한번에 deque

 

2) excelsior-cjh.tistory.com/96

collections 모듈 - deque