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

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

 

초기 문제 접근

 

배열을 이용해보자

command 열 순서대로 명령수행해보자

-->효율성,정확성 모두 통과못함

 

힌트

링크드 리스트를 활용하자

노드 당 좌우 링크를 연결해주는 리스트를 생성합니다.

삭제,복구를 해줄 때

링크를 설정해주면 됩니다.

시간초과가 날까 걱정했는데

문제 내에서

"X의 총 합이 1,000,000 이하인 경우"

라고 못을 박았기 때문에

저렇게 구현해도 시간초과 문제는 발생하지 않습니다.

 

코드

class Node:
    def __init__(self, left=None, right=None):
        self.remove = False
        self.left = left
        self.right = right


def solution(n, k, cmd):
    answer = ''

    #     data=[i for i in range(n)]

    #     now=k

    #     erase=[]
    #     backup=[]
    #     for command in cmd:
    #         nCommand=command.split()
    #         if nCommand[0]=='D' and now+int(nCommand[1])<len(data):
    #             now+=int(nCommand[1])
    #         elif nCommand[0]=='U' and now-int(nCommand[1])>=0:
    #             now-=int(nCommand[1])

    #         elif nCommand[0]=='C':
    #             backup.append(data[now])
    #             erase.append(data[now])
    #             data.pop(now)

    #         elif nCommand[0]=='Z' and backup:
    #             back=backup.pop()
    #             ind=erase.index(back)
    #             erase.pop(ind)
    #             data.insert(back,back)

    #     nums=["X"]*n
    #     for nu in data:
    #         nums[nu]="O"

    #     for n in nums:
    #         answer+=n

    table = [Node(i - 1, i + 1) for i in range(n)]
    table[0].left = None
    table[n - 1].right = None
    now = k
    stack = []
    for command in cmd:
        nCommand = command.split()
        # 아래
        if nCommand[0] == 'D':
            for _ in range(int(nCommand[1])):
                now = table[now].right
        # 위로
        elif nCommand[0] == 'U':
            for _ in range(int(nCommand[1])):
                now = table[now].left
        # 지우기
        elif nCommand[0] == 'C':
            stack.append(now)
            table[now].remove = True

            # 왼,오 링크를 다르게 설정해야함
            # 마지막 행을 지울 때 주의해야함
            nLeft = table[now].left
            nRight = table[now].right

            # 왼쪽링크 설정
            if not nLeft == None:
                table[nLeft].right = nRight

            # 오른쪽링크 설정
            # 마지막 행이 아니라면
            if nRight:
                table[nRight].left = nLeft
                now = nRight
            # 마지막행이라면
            else:
                now = nLeft
        # 되돌리기
        else:
            c = stack.pop()
            table[c].remove = False
            nLeft = table[c].left
            nRight = table[c].right

            # 링크도 다시 복구
            # 단, 복원된 행이 첫행,끝행인지 아닌지 여부에 따라 복원가능설정
            if nLeft:
                table[nLeft].right = c
            if nRight:
                table[nRight].left = c

    answer = ""
    for i in range(n):
        if table[i].remove:
            answer += "X"
        else:
            answer += "O"
    return answer