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

---

1. 코드

from collections import defaultdict

"""
	Point
    1. 리스트는 O(N) 접근 속도 -> 사전형 사용
    2. 실제로 리스트 구현하지 않고 사전형으로 더블 링크드 리스트 형태 구현
    3. 실제로 노드 삭제 안함
"""


def solution(n, k, cmd):
    answer = ''
    d = defaultdict()
    for i in range(n):
        d[i] = [i - 1, i + 1]
    d[0][0] = d[n - 1][1] = None

    stack = []
    ptr = k
    for i in cmd:
        c = i.split()
        if c[0] == 'D':
            for _ in range(int(c[1])):
                ptr = d[ptr][1]
        elif c[0] == 'U':
            for _ in range(int(c[1])):
                ptr = d[ptr][0]

        elif c[0] == 'C':
            if d[ptr][0] is None:
                next = d[ptr][1]
                d[next][0] = None
                stack.append(ptr)
                ptr = next
            elif d[ptr][1] is None:
                prev = d[ptr][0]
                d[prev][1] = None
                stack.append(ptr)
                ptr = prev
            else:
                prev = d[ptr][0]
                next = d[ptr][1]
                d[prev][1] = d[ptr][1]
                d[next][0] = d[ptr][0]
                stack.append(ptr)
                ptr = next
        else:
            if stack:
                z = stack.pop()
                if d[z][0] is None:
                    next = d[z][1]
                    d[next][0] = z
                elif d[z][1] is None:
                    prev = d[z][0]
                    d[prev][1] = z
                else:
                    prev = d[z][0]
                    next = d[z][1]
                    d[prev][1] = z
                    d[next][0] = z

    for i in stack:
        d[i] = 'X'

    for i in range(n):
        if d[i] == 'X':
            answer += 'X'
        else:
            answer += 'O'
    return answer


print(solution(8, 2, ["D 2", "C", "U 3", "C", "D 4", "C", "U 2", "Z", "Z"]))

---

2. 후기

7시간 정도 걸린 것 같다. 처음에는 직접 양방향 리스트를 구현했는데 테스트케이스에서 너무 많이 틀려서 방법을 바꿨다.

TC에서 6개 정도의 런타임에러가 출력됐는데 검색을 해봐도 런타임 에러에 대한 해답은 없었다. 그래서 그냥 정답이 나올 때까지 계속 제출해봤다.

문제의 원인은 내가 생각했을 때 아래가 원인이었던 것 같다.

# 오답 방식
if ptr == 0:
	...
elif ptr == n - 1:
	...
    
# 정답 방식
if d[ptr][0] is None:
	...
elif d[ptr][1] is None:
	...

노드를 제거(부활)할 때 첫 노드와 마지막 노드인지 조건문으로 판단하는 부분이다.
오답 방식에서는 단순히 첫 번째 항이라서 0, 마지막 항이니까 n-1이라고 생각했다.
하지만 이 부분은 탐색하는 인덱스가 고정값이므로 잘못된 코드이다.

---

• 사전형을 사용하면 원하는 인덱스에 O(1)로 접근할 수 있기 때문에 직접 리스트를 구현하지 않고도 리스트에서 이동하는 것과 같은 움직임을 구현할 수 있다.

• 실제로 노드를 삭제하지 않아야 한다. 삭제할 경우 원래 값을 불러올 수 없다.

• 이해하기 쉬운 공식 해설을 읽어보자.
  https://tech.kakao.com/2021/07/08/2021-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EC%9D%B8%ED%84%B4%EC%8B%AD-for-tech-developers-%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%B4%EC%84%A4/