제목 그대로 Linked List를 Python으로 구현해보려 한다.
갑자기 포스팅하는 이유는.. 최근 실제 코테 환경에서
외부 라이브러리 활용이 불가능한 경우를 겪었기 때문이다.

한 문제에서 완전 탐색을 하기 위해 습관처럼 다음을 사용했다.

from itertools import combinations

파이썬에서 조합의 모둔 경우를 탐색할 때 자주 활용하는 패키진데,
시험 환경에서는 이를 막아놓아 크게 당황했다.

결국 직접 구현해 어찌저찌 풀긴 했지만,
여기서 30분 정도 시간을 낭비해 시험을 망쳐버렸다.

이에 정말 기본적인 라이브러리(collections 등)외 모든 것들은
웬만하면 직접 구현해보자는 취지로 이번 포스팅을 작성한다.

이번에도 문제를 풀며 구현을 진행하겠다.
문제는 2021 카카오 채용연계형 인턴십 '표 편집' 문제이다.

---

0. 문제 설명

위 그림과 같이 표가 주어진다.

표는 파란색 부분처럼 현재 선택된 행(이하 cursor)이 존재하고,
이 cursor를 위 아래로 움직일 수 있는
엑셀과 비슷한 형태라고 보면 된다.

이제 이 표에 특정 작업을 할거고,
모든 작업이 끝난 뒤 표에 남아있는 행만 "O"표시하여
"OXOOOXXOO"와 같은 형식으로 return 해주면 되는 문제다.

작업은 다음과 같다.

"U x": x만큼 위로 이동
"D x": x만큼 아래로 이동
"C": 현재 선택된 행을 삭제
"Z": 방금 삭제한 행을 복구

현재 선택된 행을 삭제하면 바로 아래에 있는 행이 cursor가 되며,
맨 아래 행을 삭제하면 바로 위에 있는 행이 cursor가 된다.

행을 복구하면 삭제되기 전 있던 자리로 돌아가고, cursor에는 변화가 없다.

---

1. Linked List란?

리스트를 구성하는 각 원소가 다음, 이전 원소를 pointer로 가리키고 있는 형태의 자료구조.

가장 기본적인 자료구조니, 모두 알 것이라고 생각한다.
이 문제를 Linked List 통해 풀어야겠다고 생각한 이유는 다음과 같다.

cursor의 이동이 용이함

cursor를 위나 아래로 x회 이동할 때, 삭제된 원소를 건너뛰어야 한다.

이걸 배열로 구현하려면 각 원소의 삭제 여부를 flag로 저장해야하며,
삭제된 원소라면 건너뛰는 과정을 반복해야한다.

이렇게 되면, 이론상 커서 이동 한 번에 수행해야 하는 연산이
최대 20만회까지 커질 수 있다. (처음과 끝행만 남아있다고 가정)

작게 따져 10만회라고 쳐도, 이 연산을 100번만 반복해도 1,000만회의 연산이 실행되기 때문에, 가뿐하게 주어진 시간을 초과한다.

값 삭제가 용이함

Linked List에서의 값 삭제는 사실 진짜 '삭제'가 아니다.
정확히는 '노드 사이의 연결을 끊고 다시 붙인다'는 개념이다.

따라서 노드는 그대로 살아있게 되고, 참조 pointer 값만 바뀐다.
이로써 삭제에 들어가는 비용이 줄어들게 된다.

반면 배열은 특정 값을 삭제하려면 배열 자체를 재생성해야한다.

실행 취소가 용이함

Linked List는 자신의 위치를 '내가 어떤 노드 사이에 있나?'로
기억하고 있기 때문에, 삭제후 원래 자리로 돌리기가 용이하다.

반면 배열은 특정 위치에 값을 삽입하려면 배열 자체를 재생성해야한다.

---

2. 구현

1. Node class 구현
2. LinkedList class 구현

큰 맥락은 위와 같다. 각각 자세하게 코드로 뜯어보자.

Node Class 구현

class Node:
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.child = None

먼저 id를 받아 node의 value값으로 저장하고,
연결 정보인 parent와 child를 필드로 구성한다.

id같은 경우 필수는 아니지만,
마지막에 최종 삭제 여부를 확인하기 위해 저장하는게 좋다.

LinkedList Class 구현

class LinkedList:
    def __init__(self):
        self.root = None
        self.leaf = None
        self.stack = []
    
    def set_cursor(self, k):
        self.cursor = self.root
        for _ in range(k):
            self.cursor = self.cursor.child

먼저 field를 설정해주는데, root와 leaf, stack, cursor를 구성한다.

기능상으로는 leaf가 굳이 필요 없을수도 있는데,
여기서는 배열의 값이 최대 100만이나 되므로
leaf단의 노드를 기억해서 새 Node를 효율적으로 추가할 수 있게 한다.

또, stack을 두어 삭제된 노드를 잠시 저장하는 공간을 마련해준다.

마지막으로 cursor field의 초기값을 지정해줘야하는데,
이는 리스트가 완성된 후에 지정해야 하므로 별도의 메소드를 두었다.

def append(self, node):
    if self.root is None:
        self.root = node
        self.leaf = node
    else:
        self.leaf.child, node.parent = node, self.leaf
        self.leaf = node

값을 추가하는건 간단하다.

root가 없다면 직접 root와 leaf를 지정해주고,
있다면 leaf의 자식에 추가한 후 leaf 노드를 변경해주면 된다.

def up(self, x):
    for _ in range(x):
        if self.cursor.parent is None:
            break
        self.cursor = self.cursor.parent
    
def down(self, x):
    for _ in range(x):
        if self.cursor.child is None:
            break
        self.cursor = self.cursor.child

다음으로 커서의 이동 메소드다.

주어진 x값 만큼 해당 방향으로 이동하며,
만약 root나 leaf에 다다랐다면 그대로 종료한다.

def delete(self):
    parent = self.cursor.parent
    child = self.cursor.child
    self.stack.append(self.cursor)
    if parent is None:
        self.cursor = child
        self.root = child
        child.parent = None
    elif child is None:
        self.cursor = parent
        self.leaf = parent
        parent.child = None
    else:
        self.cursor = child
        parent.child, child.parent = child, parent

다음으로 값을 삭제하는 메소드다.

위에서 언급한 것처럼, 부모 노드와 자식 노드를 찾아 둘을 엮어주면 된다.
부모/자식 노드가 root/leaf일 경우만 조심해서 처리하면 어렵지 않다.

삭제한 노드는 나중에 복구할 수 있도록 stack에 쌓아주는 것을 잊지 말자.

def cancel(self):
    node = self.stack.pop()
    parent = node.parent
    child = node.child
    if parent is None:
        self.root = node
        child.parent = node
    elif child is None:
        self.leaf = node
        parent.child = node
    else:
        parent.child, child.parent = node, node

마지막으로 복구 메소드다.

stack에서 최근 삭제한 node를 가져와서 다시 이어붙어준다.
여기서 Linked List의 장점이 드러나는데,
Node 자체에 부모와 자식 노드가 이미 저장되어있으므로
별다른 조치 없이 해당 노드를 찾아 다시 이어줄 수 있다.

처음 구현할때는 '혹시 복구하려는 노드의 부모나 자식노드가 stack에 있으면 어떡하지?'라고 생각했는데,
조금만 생각해보면 이럴 일은 없다는 것을 알 수 있다.

이렇게 완성된 LinkedList class 전체코드는 아래와 같다.

class LinkedList:
    def __init__(self):
        self.root = None
        self.leaf = None
        self.stack = []
        
    def set_cursor(self, k):
        self.cursor = self.root
        for _ in range(k):
            self.cursor = self.cursor.child
        
    def append(self, node):
        if self.root is None:
            self.root = node
            self.leaf = node
        else:
            self.leaf.child, node.parent = node, self.leaf
            self.leaf = node
    
    def up(self, x):
        for _ in range(x):
            if self.cursor.parent is None:
                break
            self.cursor = self.cursor.parent
    
    def down(self, x):
        for _ in range(x):
            if self.cursor.child is None:
                break
            self.cursor = self.cursor.child
        
    def delete(self):
        parent = self.cursor.parent
        child = self.cursor.child
        self.stack.append(self.cursor)
        if parent is None:
            self.cursor = child
            self.root = child
            child.parent = None
        elif child is None:
            self.cursor = parent
            self.leaf = parent
            parent.child = None
        else:
            self.cursor = child
            parent.child, child.parent = child, parent
            
    def cancel(self):
        node = self.stack.pop()
        parent = node.parent
        child = node.child
        if parent is None:
            self.root = node
            child.parent = node
        elif child is None:
            self.leaf = node
            parent.child = node
        else:
            parent.child, child.parent = node, node

---

3. 풀이

def solution(n, k, cmd):
    linked_list = LinkedList()
    for id in range(n):
        linked_list.append(Node(id))
    linked_list.set_cursor(k)
    for c in cmd:
        if c[0]=="U":
            linked_list.up(int(c[2:]))
        elif c[0]=="D":
            linked_list.down(int(c[2:]))
        elif c=="C":
            linked_list.delete()
        else:
            linked_list.cancel()
    answer = ["O"]*n
    for node in linked_list.stack:
        answer[node.id] = "X"
    return "".join(answer)

class를 완성했다면, 푸는데 어려울 건 없다.

list를 만들어 모든 node를 추가해주고,
command에 따라 각 메소드를 실행해준다.

마지막으로 "OOOO...OO"로 초기화된 배열을 구성한 뒤,
list의 stack에 남아있는(삭제된) node의 id만 X로 바꿔주면 끝!!