[프로그래머스] 표 편집 (Python)

https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

연결리스트를 활용해서 풀어야 하는 문제다

트리나 연결리스트를 활용하는 방법을 정리해놔야겠다.

 

class Node:
    def __init__(self):
        self.prev = None
        self.next = None
        self.removed = False
        
def solution(n, k, cmd):
    linkedList = [Node() for _ in range(n)]
    for i in range(1,n):
        linkedList[i].prev = linkedList[i-1]
        linkedList[i-1].next = linkedList[i]
    deleted = []
    cursor = linkedList[k]
    for command in cmd:
        if command[0] == 'U':
            x = int(command[2:])
            for _ in range(x):
                cursor = cursor.prev
        elif command[0] == 'D':
            x = int(command[2:])
            for _ in range(x):
                cursor = cursor.next
        elif command[0] == 'C':
            deleted.append(cursor)
            cursor.removed = True
            up = cursor.prev
            down = cursor.next
            if up:
                up.next = down
            if down:
                down.prev = up
                cursor = down
            else:
                cursor = up
        else:
            node = deleted.pop()
            node.removed = False
            up = node.prev
            down = node.next
            if up:
                up.next = node
            if down:
                down.prev = node
    answer = ''
    for i in range(n):
        if linkedList[i].removed :
            answer +='X'
        else:
            answer +='O'
    return answer