[프로그래머스 LV.3] 표 편집 (파이썬/python)

https://programmers.co.kr/learn/courses/30/lessons/81303?language=python3 

코딩테스트 연습 - 표 편집

 

애좀 먹었던문제; 

 

맨 처음 구현은 삭제된 리스트들을 디큐에 넣은다음

모든 연산을 마치고 복원하는 식으로 구현을 했었는데 복원이 생각보다 잘 안됐다

 

다른분들 코드를 조금 참고했는데

삭제를 할시 링크드리스트(내 코드에서는 딕셔너리로 가라 링크드리스트를 구현했음)를 이용해서 삭제된 노드, 그리고 그 상황에서 앞 뒤 노드들의 연결관계를 표시해주며 코드를 구현하면 됐다

 

 

# C 명령에 의한 삭제
def delete(answer, pointer, delete_stack, linked_table):
    next_pointer = pointer

    answer[pointer] = "X"
    prev_, next_ = linked_table[pointer]
    delete_stack.append([prev_, next_, pointer])

    # 포인터 위치 변경
    if next_ is None:
        next_pointer = prev_
    else:
        next_pointer = next_

    # 삭제된 노드의 앞 뒤 노드를 서로 연결
    if prev_ is not None:
        linked_table[prev_][1] = next_
    if next_ is not None:
        linked_table[next_][0] = prev_

    return next_pointer


# Z 명령에 의한 복구
def regeneration(answer, delete_stack, linked_table):
    prev_, next_, pointer_ = delete_stack.pop()

    answer[pointer_] = "O"

    if prev_ is not None:
        linked_table[prev_][1] = pointer_
    if next_ is not None:
        linked_table[next_][0] = pointer_


# 명령 체크
def cmdCheck(answer, pointer, cmd, delete_stack, linked_table):
    next_pointer = pointer

    if cmd[0] == "U":
        c, step = cmd.split(" ")
        for i in range(int(step)):
            next_pointer = linked_table[next_pointer][0]

    elif cmd[0] == "D":
        c, step = cmd.split(" ")
        for i in range(int(step)):
            next_pointer = linked_table[next_pointer][1]

    elif cmd[0] == "C":
        next_pointer = delete(answer, pointer, delete_stack, linked_table)

    elif cmd[0] == "Z":
        regeneration(answer, delete_stack, linked_table)

    return next_pointer


def solution(n, k, cmd):
    # 정답
    answer = ["O"] * n
    # 현재 가리키는 위치
    pointer = k
    # 삭제된 명령어 저장 큐
    delete_stack = []
    # 현재 표의 상태
    linked_table = {i: [i - 1, i + 1] for i in range(n)}
    linked_table[0][0] = None
    linked_table[n - 1][1] = None

    for c in cmd:
        pointer = cmdCheck(answer, pointer, c, delete_stack, linked_table)

    answer = "".join(answer)

    return answer