[Python] 1021번 : 회전하는 큐

 

문제 설명 3줄 요약

 

1. 3가지 연산이 가능한 큐

2. 첫 번째 요소 빼기, 두 번째 원소 왼쪽 한칸 이동, 세 번째 원소 오른쪽 한칸 이동

3. 주어진 원소를 빼려고 할 때, 왼쪽 또는 오른쪽 이동의 최솟값은 몇 번 일까요?

 

 

기존의 리스트를 사용하기엔

왼쪽 또는 오른쪽으로 이동할 경우,

모든 원소를 한칸씩 값을 옮겨줘야한다는 문제가 생기기 때문에

링크드리스트로 값을 연결해주어 해결하였다.

 

from sys import stdin
 
# 링크드리스트에 사용할 원소
class Node:
    def __init__(self,data,next=None):
        self.data = data
        self.next = next
 
# 링크드리스트 및 기능
class LinkedList:
    def __init__(self):
        self.node_cnt = 0
        self.head = None
 
	## 첫 번째 원소 삽입
    def add_first(self, data):
        pointer = self.head
        self.head = Node(data, pointer)
        self.node_cnt += 1
 
	## 이후 원소들 삽입
    def add_last(self, data):
        pointer = self.head
        while pointer.next:
            pointer = pointer.next
 
        pointer.next = Node(data, None)
        self.node_cnt += 1
 
	## 해당 값을 가지고 있는 원소 찾기
    def find(self, data):
        pointer = self.head
        cnt = 0
        while pointer.data != data:
            pointer = pointer.next
            cnt += 1
        return cnt
 
	## 첫 번째, 원소 제거
    def pop(self):
        self.head = self.head.next
        self.node_cnt -= 1
 
	## 두 번째, 왼쪽 이동 
    def Left(self,L):
        for _ in range(L):
            node = self.head
            while node.next:
                node = node.next
            node.next = self.head
            self.head = self.head.next
            node.next.next = None
 
	## 세 번째, 오른쪽 이동
    def Right(self,R):
        for _ in range(R):
            node = self.head
            while node.next.next:
                node = node.next
            node.next.next = self.head
            self.head = node.next
            node.next = None
 
 
 
if __name__ == "__main__":
	## 큐의 크기 N, 뽑으려 하는 수 M개
    ## N <= 50, M <= N
    N, M = map(int, stdin.readline().split())
    ll = LinkedList()
 
    result = 0
	
    for i in range(1,N+1):
        if i == 1:
            ll.add_first(i)
        else:
            ll.add_last(i)
 
    ## 뽑고자 하는 수
    num = list(map(int, stdin.readline().split()))
 
    for i in num:
        move = ll.find(i)
 
        if (move == 0):
            ll.pop()
        else:
            if(move <= ll.node_cnt-move):
                result += move
                ll.Left(move)
                ll.pop()
            else:
                result += ll.node_cnt-move     
                ll.Right(ll.node_cnt-move)
                ll.pop()                          
    print(result)

 

큐를 대신하는 자료구조를 링크드 리스트로 구현해보는 문제였다.

두 번째, 세 번째 기능을 구현할 때,

원소간 연결과 끊음에서 살짝 혼돈이 있었지만,

그림을 그리며 고민해보니 풀 수 있었다.

 

끝!