Programmers. 표 편집

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 표 편집

문제 풀이

유니온 파인드로 풀 수 있지 않을까 생각했지만 삭제 순간은 현재 지점을 지우면 되지만 복구 지점은 이전 위치에 복구해야 한다는 점과 마지막으로 삭제한 노드의 양쪽 지점은 삭제되지 않은 상태라는 점을 참고해 이중 연결리스트라면 O(1)에 가능할 수도 있겠다 생각했다. C라면 포인터의 개념을, 파이썬이라면 메모리가 가리키는 변수공간에 대한 고려를 할 수 있는가 판단하는 문제였다고 생각한다. 시간 내에 문제를 해결하긴 했지만 해설을 보니 세그먼트나 팬윅트리로도 해결할 수 있다는데 일단 스킵.

• 현재 값, 좌측, 우측 포인터를 변수로 갖는 리스트 노드 정의
• 커서를 다루기 위해 양쪽 끝을 -1로 무효 노드로 두고 사이에 배열을 순회하면서 넣는다. 별도의 동일한 변수를 연결시켜서 한 변수는 그대로 첫번째를 가리키게 한 뒤 k번 이동해서 초기 커서의 위치를 설정한다.
• 각 명령에 따라 행동하되 C입력 시 스택에 삭제 노드의 왼, 오른쪽을 초기화하지 않고 그대로 스택에 넣어 복구 시 찾아갈 수 있도록 한다. 그리고 커서를 조건에 맞춰서 이동시킨다.
• Z입력 시 스택에 가장 마지막으로 삭제된 노드를 가져와 이전 노드와 이후 노드를 변수에 할당해 다시 복구시킨다.

코드가 굉장히 길어지는 문제였는데도 정답률이 꽤 높다는게 좌절스럽다.

python 코드

class ListNode(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def solution(n, k, cmd):
    cur = head = node = ListNode(-1)
    for i in range(n):
        new = ListNode(i)
        node.right = new
        new.left = node
        node = node.right
    new = tail = ListNode(-1)
    node.right = new
    new.left = node
    node = node.right
    for i in range(k + 1):
        cur = cur.right
    stack = []
    for i in range(len(cmd)):
        if len(cmd[i]) == 1:
            if cmd[i] == "C":
                if cur.right.val == -1:
                    stack.append(cur)
                    cur.left.right, cur.right.left, cur = cur.right, cur.left, cur.left
                else:
                    stack.append(cur)
                    cur.left.right, cur.right.left, cur = cur.right, cur.left, cur.right
            elif cmd[i] == "Z":
                reg_node = stack.pop()
                prev = reg_node.left
                nxt = reg_node.right
                prev.right = reg_node
                nxt.left = reg_node
        else:
            op, x = cmd[i].split()
            if op == "U":
                for _ in range(int(x)):
                    cur = cur.left
            elif op == "D":
                for _ in range(int(x)):
                    cur = cur.right
    answer = ["X" for _ in range(n)]
    buf = []
    while head:
        buf.append(head.val)
        head = head.right
    cnt = 0
    for b in buf[1:-1]:
        answer[b] = "O"
    return "".join(answer)