효율성이 70%를 차지한다
링크드리스트 + 스택이 결합된 문제

삽입 삭제가 빠른 배열 - 링크드 리스트
삭제한 정보가 최근 순서대로 복구 - 스택

1. 딕셔너리로 구현

링크드리스트를 직접 구현할 것인가?
단순 삽입 삭제라면 딕셔너리로 해결할 수 있다

data[i] = [i - 1, i + 1]: i번째 row의 prev, next를 원소가 2개인 리스트(튜플)로 표현할 수 있다.

def solution(n, k, cmd):
    stack = []
    data = {i: [i - 1, i + 1] for i in range(1, n)}
    data[0] = [n - 1, 1]
    data[n - 1] = [n - 2, 0]
    cur = k
    
    for cmd_row in cmd:
        if cmd_row == 'Z':
            pos, item = stack.pop()
            data[pos] = item
            pre, nxt = item
            data[pre][1] = pos
            data[nxt][0] = pos
            
        elif cmd_row == 'C':
            pre, nxt = data[cur]
            data[pre][1] = nxt
            data[nxt][0] = pre

            stack.append([cur, data[cur]])
            del data[cur]
            if nxt < cur:
                cur = pre
            else:
                cur = nxt

        else:
            opt, step = cmd_row.split()
            step = int(step)
            if opt == 'U':
                for _ in range(step):
                    cur = data[cur][0]
            else:
                for _ in range(step):
                    cur = data[cur][1]
        #print(data, stack)
    answer = ''
    for i in range(n):
        if i in data:
            answer += 'O'
        else:
            answer += 'X'
    return answer

2. Doubly Linked List로 구현

앞뒤로 리스트를 순회해야하므로 양방향 링크드리스트를 구현한다.
삽입/삭제의 일관성을 유지하기 위해 head, tail에 dummy node를 넣었다.

class Node:
    def __init__(self, data = None):
        self.data = data
        self.prev = None
        self.next = None


class DLL:
    '''Doubly Linked List'''
    
    def __init__(self, n, k):
        ''' Initialize Doubly Linked Lst (DLL)
            n (int): Initial size of the DLL
            k (int): Initial position of the DLL
        '''
        self.n = n
        self.k = k
        self.stack = []
        self.head = Node()
        self.tail = Node()
        
        # make dummy node
        self.head.next = self.tail
        self.tail.prev = self.head

        # initialize Doubly Linked List
        for i in range(self.n):
            node = Node(i)
            node.prev = self.tail.prev
            node.next = self.tail
        
            self.tail.prev.next = node
            self.tail.prev = node

        # setting CUR_NODE
        self.cur = self.head.next
        for _ in range(self.k):
            self.cur = self.cur.next

    def go_next(self, count):
        for _ in range(count):
            if self.cur.next != self.tail:
                self.cur = self.cur.next
            else:
                break

    def go_prev(self, count):
        for _ in range(count):
            if self.cur.prev != self.head:
                self.cur = self.cur.prev
            else:
                break
        
    def pop(self):
        self.stack.append(self.cur)
        self.cur.prev.next = self.cur.next
        self.cur.next.prev = self.cur.prev

        # resetting CURRENT NODE
        self.cur = self.cur.next
        if self.cur == self.tail:
            self.cur = self.tail.prev

    def roll_back(self):
        node = self.stack.pop()
        node.prev.next = node
        node.next.prev = node

    def status(self):
        container = {}
        node = self.head.next
        while node != self.tail:
            container[node.data] = 1
            node = node.next
        result = ''
        for i in range(self.n):
            if i in container:
                result += 'O'
            else:
                result += 'X'

        return result


    def __str__(self):
        ''' Print the DLL '''
        ret = '['
        node = self.head.next
        while node != self.tail:
            ret += ' ' + str(node.data)
            node = node.next
        ret += ' ]'
        return ret



def solution(n, k, cmd):
    dll = DLL(n, k)
    for cmd_row in cmd:
        if cmd_row == 'C':
            dll.pop()
        elif cmd_row == 'Z':
            dll.roll_back()
        else:
            opt, count = cmd_row.split()
            count = int(count)
            if opt == 'U':
                dll.go_prev(count)
            else:
                dll.go_next(count)
    
    answer = dll.status()
    return answer