Baekjoon 백준 알고리즘 - 회전하는 큐( 1021 )

1. 문제 소개

• 자료 구조 큐를 이용해야 하는 문제다.

 

2. 코드

from collections import deque

def set_test_case():
    in_line = input().split(" ")
    n,m = int(in_line[0]),int(in_line[1])

    in_line = input().split(" ")
    pop_list = [int(x) for x in in_line]

    return n,m,pop_list

def pop_simulate(q,v):
    dir= 1 if q.index(v) > len(q)//2 else - 1
    turn=0

    while(True):
        if q[0] == v:
            q.popleft()
            break
            
        else:
            q.rotate(dir)
            turn += 1
    return turn

def solution():
    n,m,pop_list = set_test_case()
    turns = []
    q = deque([i for i in range(1,n+1)])

    #q.rotate(1) # to right
    
    for v in pop_list:
        result = pop_simulate(q,v)
        turns +=[result]
    print(sum(turns))


if __name__=="__main__":
    solution()

 

3. 코멘트

• pop 할 원소의 위치가 큐 길이의 중앙 값을 기준으로 비교 후에 왼쪽으로 이동시킬 지 , 오른쪽으로 이동시킬 지 방향을 구한다.
• 2초 제한과 50의 테스트케이스 정도는 시뮬레이션 방식으로 통과가 가능할 것 같아, 간단한 시뮬레이션을 구현했다.
• 그 동안 프로젝트 때문에 알고리즘 스터디를 오랜만에 참여했다. 앞으로는 더 열심히 하자.