프로그래머스_표 편집

문제

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

코딩테스트 연습 - 표 편집

풀이

Linked List

노드의 포인터가 다음이나 이전의 노드와의 연결을 담당

# Linked List
nodes = {i:[(i+n-1)%n, (i+1)%n] for i in range(n)}

Linked List

• 삽입 Z

• 삭제 C

어려웠던 부분

1. 되돌리기

되돌리기를 할 때 링크드 리스트 전체를 stack에 저장했다. 그래서 그런지 효율성 테스트를 통과하지 못했다. 다른 사람들의 코드를 보니 노드 하나만을 저장하더라! 

 

2. 링크드 리스트

굳이 원형으로 연결되어야 할까?라는 생각에 아래와 같이 표현하였다. 이렇게 표현하니 코드가 중간에 꼬이더라...

시도1

코드

def solution(n, k, cmd):
    # Linked List
    nodes = {i:[(i+n-1)%n, (i+1)%n] for i in range(n)}
    stack = list()
    
    for c in cmd : 
        if "U" in c : # ↑
            m = int(c.split()[-1])
            for i in range(m) : k = nodes[k][0]
                
        elif "D" in c : # ↓
            m = int(c.split()[-1])
            for i in range(m) : k = nodes[k][1]
                
        elif "C" in c : 
            # disconnect
            pre, post = nodes[k]
            nodes[pre][1] = nodes[k][1]
            nodes[post][0] = nodes[k][0]
            stack.append([k, *nodes[k]])
            # delete
            tmp = nodes[k]
            del nodes[k]
            # point
            if tmp[1]==0 : k = tmp[0]
            else : k = tmp[1]
            
        elif "Z" in c : # 끼워넣기
            cur, pre, post = stack.pop()
            nodes[cur] = [pre, post]
            nodes[pre][1] = cur
            nodes[post][0] = cur

    ans = ""
    for i in range(n) : 
        if i in nodes : ans += "O"
        else : ans += "X"
    return ans