[프로그래머스] 표편집 (Python)

❓문제

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

❗풀이

🙈 본래 의도

• 현재 선택된 행의 이동, 삭제 그리고 삭제된 행 복구 명령어가 존재함.
• stack 과 크게 다르지 않다고 생각하였고 삭제된 경우 'X', 존재하는 경우 'O'로 표시
• 삭제할 경우, delete_list 에 삭제된 index를 저장하여 stack으로 활용
• 따라서 위/아래로 이동할 시에 O/X 여부를 판단하여 이동

하면 될 것으로 생각했으나...

→ o/x 여부를 확인하는 과정에서 시간초과 발생 및 정확성 문제 발생 😣

🙉 새로운 해답

그래서 다른 풀이들을 봐본 결과, 연결 리스트 (Linked List)에 대한 공부를 한 뒤, 

다시 적용하기로 했다.

https://onyodev.tistory.com/5

이중 연결 리스트의 개념을 적용하여

현재 node를 key로 삼고

prev, next 노드의 쌍을 value로 갖는 dict를 생성하여 풀기로 하였다. 

• 삭제 시, prev 노드의 next값과 next 노드의 prev값을 수정해주고 
• 복구 시, prev 노드와 next 노드를 찾아 다시 값을 갱신해준다.
• 그리고 이동 시, 이동 횟수만큼 연결(prev or next)을 타고 간다.

💻 코드 

'''
현재선택된 행 = now
U X: 현재선택된 행 - X 행
D X: 현재선택된 행 + X 행
C : 현재선택된 행 삭제 -> 바로 아래 행 선택 (마지막 행 삭제의 경우, 바로 윗 행)
Z : 가장 최근에 삭제된 행 복구
n: 행 개수
k: 처음 선택된 행의 위치
'''
 
def solution(n, k, cmd):
    now = k
    table = {i:[i-1, i+1] for i in range(n)}
    table[0] = [None, 1]
    table[n-1] = [n-2, None]    
    del_list = []
    check = ['O']*n
    
    for c in cmd:
        if c == 'C':
            check[now] = 'X'
            prev, next = table[now]
            del_list.append((prev,now,next)) 
            now = table[now][0] if next == None else table[now][1]
            
            if prev == None:
                table[next][0] = None
            elif next == None:
                table[prev][1] = None
            else:
                table[next][0] = prev
                table[prev][1] = next
                
                               
        elif c == 'Z':
            prev, that, next  = del_list.pop()
            check[that] = 'O'
            if prev == None:
                table[next][0] = that
            elif next == None:
                table[prev][1] = that
            else:
                table[prev][1] = that
                table[next][0] = that
        
        else: 
            c1, c2 = list(map(str, c.split()))
 
            if c1 == 'U':
                for _ in range(int(c2)):
                    now = table[now][0]
            elif c1 == 'D':
                for _ in range(int(c2)):
                    now = table[now][1]
    answer = ''.join(check)
    return answer