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

난이도 : LV 3

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/81303

문제해결 아이디어

• 처음 문제풀때 리스트에 순서들을 담고 pop 과 insert를 활용하여 명령어를 수행했었다. => 효율성 테스트 탈락
• 어떻게 시간초과를 해결할지 모르겠어서 다른사람풀이를 참고했다.
• dict를 이용해 특정열에 대한 검색시간을 줄였다.
• 그리고 dict에 해당 인덱스와 prev, next를 저장해주는 방법을 통해서 특정열에 접근하는 시간복잡도를 O(1)으로 줄였다.

소스코드

def solution(n, k, cmd):
    link = { i : [i-1, i+1] for i in range(n) }
    link[0] = [None, 1]
    link[n-1] = [n-2, None]
    cur = k
    ans = ['O'] * n
    stack = []
    
    for c in cmd:
        if c == 'C':
            ans[cur] = 'X'
            prev,next = link[cur]
            stack.append([prev,cur,next])
            
            if next == None:
                cur = link[cur][0]
            else:
                cur = link[cur][1]
            
            if prev == None:
                link[next][0] = None
            elif next == None:
                link[prev][1] = None
            else:
                link[prev][1] = next
                link[next][0] = prev
            
        elif c == 'Z':
            prev, now , next = stack.pop()
            ans[now] = 'O'
            
            if prev == None:
                link[next][0] = now
            elif next == None:
                link[prev][1] = now
            else:
                link[next][0] = now
                link[prev][1] = now
        else:
            c1, c2 = c.split()
            if c1 == 'U':
                for _ in range(int(c2)):
                    cur = link[cur][0]
            else:
                for _ in range(int(c2)):
                    cur = link[cur][1]
                
    return "".join(ans)