프로그래머스_표_편집

[문제 링크]

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

[입출력 예]

n	k	cmd	result
8	2	["D 2","C","U 3","C","D 4","C","U 2","Z","Z"]	"OOOOXOOO"
8	2	["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"]	"OOXOXOOO"

[소스코드1]

출처: https://ckd2806.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%91%9C-%ED%8E%B8%EC%A7%91

def solution(n, k, cmd):
    answer = ''
    # 딕셔너리로 링크드리스트 만듬. key:value는 노드번호:[인접한 노드번호]
    # 1부터 n까지
    linked_list = {i: [i - 1, i + 1] for i in range(1, n+1)}

    # OX는 result
    OX = ["O" for i in range(1,n+1)]
    stack = []

    # 링크드리스트 노드 번호를 1~n으로 했으므로 ... 1추가
    # k는 연결리스트 노드 번호 == 현재 행 번호 + 1
    k += 1

    # cmd를 순회
    for c in cmd:
        # Down일 경우
        # k=2+1 = 3, D 2를 예로 들면,
        # k=3=>4=>5로 이동함
        if c[0] == 'D':
            for _ in range(int(c[2:])):
                k = linked_list[k][1]
        # U도 마찬가지
        elif c[0] == 'U':
            for _ in range(int(c[2:])):
                k = linked_list[k][0]
        # C의 경우 삭제 연산을 수행해야하는데, 삭제 = OX기록 바꾸기 + 스택에 기록
        # next가 마지막일 경우 연결리스트 상 prev를 따라가고, 마지막이 아니면 next를 따라감.
        elif c[0] == 'C':
            prev, next = linked_list[k]

            stack.append([prev, next, k])
            OX[k-1] = "X"

            if next == n+1:
                k = prev
            else:
                k = next
            # head일 경우 prev노드가 없음
            if prev == 0:
                linked_list[next][0] = prev
            # tail일 경우 next 노드가 없음
            elif next == n+1:
                linked_list[prev][1] = next
            else:
                linked_list[prev][1] = next
                linked_list[next][0] = prev

        elif c[0] == 'Z':
            prev, next, now = stack.pop()

            # 스택에서 빼서 OX 복원
            OX[now-1] = "O"

            if prev == 0:
                linked_list[next][0] = now
            elif next == n+1:
                linked_list[prev][1] = now
            else:
                linked_list[prev][1] = now
                linked_list[next][0] = now

    return "".join(OX)

[풀이]

1. 딕셔너리로 연결리스트 노드 번호가 인접 점들을 기억하도록 구성
2. 이동할 때 사전에 조회해서 이동하는 식
3. 삭제 시 현재 번호(k) 와 prev, next를 우선 저장하는 것에서 시작함.
4. 만약 {1:[0,2], 2:[1,3], 3:[2,4]} 에서 2가 사라진다면
   행번호 1, k = 2인 노드가 사라지는 것이고
   {1:[0,3], 3:[1,4]}로 업데이트가 되어야 함.
   따라서 삭제 연산 시 우선 k, prev, next정보를 스택에 저장하고
   head인지 tail인지 여부에 따라 업데이트.
5. 복원도 마찬가지 과정을 경우에 나눠 진행하면 됨.

[소스코드2]

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

class LinkedList:
    class Node:
        def __init__(self, num, prev):
            self.num = num
            self.prev = prev
            self.next = None

    def __init__(self, num, start):
        self.root = self.Node(0, None)
        self.current = None
        self.stack = []
        temp = self.root
        for i in range(1, num):
            new_node = self.Node(i, temp)
            temp.next = new_node
            if i == start:
                self.current = new_node
            temp = new_node

    def up(self, num):
        for _ in range(num):
            if self.current.prev:
                self.current = self.current.prev

    def down(self, num):
        for _ in range(num):
            if self.current.next:
                self.current = self.current.next

    def remove(self):
        remove_node = self.current
        self.stack.append(remove_node)
        if remove_node.next:
            if remove_node == self.root:
                self.root = remove_node.next
            self.current = remove_node.next
            self.current.prev = remove_node.prev
            if remove_node.prev:
                remove_node.prev.next = self.current
        else:
            self.current = remove_node.prev
            self.current.next = None

    def recover(self):
        recover_node = self.stack.pop()
        if recover_node.prev:
            recover_node.prev.next = recover_node
        if recover_node.next:
            recover_node.next.prev = recover_node
            if recover_node.next == self.root:
                self.root = recover_node

    def get_root(self):
        return self.root

    def __bool__(self):
        return True


def solution(n, k, cmd):
    table = LinkedList(n, k)
    for c in cmd:
        if c[0] == 'U':
            table.up(int(c.split()[1]))
        elif c[0] == 'D':
            table.down(int(c.split()[1]))
        elif c[0] == 'C':
            table.remove()
        else:
            table.recover()
    node = table.get_root()
    result = ["X"] * n
    while node:
        result[node.num] = "O"
        node = node.next
    return "".join(result)

[풀이]

1. 정식 링크드리스트 구현(양방향)
2. 클래스 안에 클래스가 정의되어 있고, 0번이 루트(헤드)
3. 노드를 정의할 때 prev를 입력하도록 되어있음.
4. up, down은 self.current를 움직임.
5. bool은 필요없음
6. 훨씬 더 짜임새 있는 풀이! 그러나, 더 느리다.