프로그래머스 표 편집

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

문제를 해결하지 못해 바킹독님의 풀이를 보았다.
이 문제의 해결법은 연결리스트였다. 연결리스트는 가장 기초적인 자료구조인데, 이를 이용한 문제를 푸는것은 이번이 처음이었다.

연결리스트를 구현하고 삽입과 삭제를 구현하고, 문제의 로직을 담으면 되는데, 연결리스트를 처음부터 다 구현하기에는 코드 양이 많아지기 때문에 바킹독님이 사용한 배열을 이용한 연결리스트 방법을 알게되었다.

연결리스트는 이 전의 노드가 앞과 뒤의 주소를 참조하는 방식을 이용해 연결하는 것이 일반적인데, 아래의 구현에서는 unused값을 이용하여 일종의 주소로 참조하여 연결한 것과 같은 효과를 내었다.
이 문제에서는 Z연산을 처리하는 것이 큰 문제인데, 연결리스트에서 어떤 값을 지우고 다시 연결한다면, 어디에 다시 연결해야 하는가의 문제가 생기게 된다. 그렇기 때문에 num2idx라는 배열을 만들어 특정 값의 인덱스를 만들어 놓은 배열을 만들었다.

mx = 1200005
data = [-1] * mx
pre = [-1] * mx
nxt = [-1] * mx
unused = 1
num2idx = [-1] * mx
def insert(address, num):
    global unused
    data[unused] = num
    pre[unused] = address
    nxt[unused] = nxt[address]
    if nxt[address] != -1:
        pre[nxt[address]] = unused
    nxt[address] = unused
    unused += 1
    return unused - 1
def erase(address):
    nxt[pre[address]] = nxt[address]
    if nxt[address] != -1:
        pre[nxt[address]] = pre[address]
        return nxt[address]
    return pre[address]
def solution(n, k, cmd):
    for i in range(n):
        num2idx[i] = insert(i, i)
    cursor = num2idx[k]
    stack = []
    for cm in cmd:
        a = cm.split(" ")
        if a[0] == 'D':
            for i in range(int(a[1])):
                cursor = nxt[cursor]
        elif a[0] == 'U':
            for i in range(int(a[1])):
                cursor = pre[cursor]
        elif a[0] == 'C':
            stack.append((data[pre[cursor]], data[cursor]))
            cursor = erase(cursor)
        elif a[0] == 'Z':
            a, b = stack.pop()
            if a == -1:
                preidx = 0
            else:
                preidx = num2idx[a]
            num2idx[b] = insert(preidx, b)

    s = ['X'] * n
    cur = nxt[0]
    while cur != -1:
        s[data[cur]] = 'O'
        cur = nxt[cur]
    return ''.join(s)

• 위와 같은 풀이도 가능하지만, 좀더 생각해보면 위의 문제에서는 주소를 참조할 필요 없이 값 자체가 주소가 될 수 있다는 점을 생각할 수 있다.

mx = 1200005
pre = [-1] * mx
nxt = [-1] * mx
def solution(n, k, cmds):
    s = ['O'] * n
    for i in range(n):
        pre[i], nxt[i] = i - 1, i + 1
    nxt[n - 1] = -1
    cursor = k
    erased = []
    for cmd in cmds:
        q = cmd.split(" ")
        if q[0] == 'U':
            for i in range(int(q[1])):
                cursor = pre[cursor]
        elif q[0] == 'D':
            for i in range(int(q[1])):
                cursor = nxt[cursor]
        elif q[0] == 'C':
            erased.append((pre[cursor], cursor, nxt[cursor]))
            if pre[cursor] != -1: nxt[pre[cursor]] = nxt[cursor]
            if nxt[cursor] != -1: pre[nxt[cursor]] = pre[cursor]
            s[cursor] = 'X'
            if nxt[cursor] != -1:
                cursor = nxt[cursor]
            else:
                cursor = pre[cursor]
        elif q[0] == 'Z':
            p, c, n = erased.pop()
            if p != -1: nxt[p] = c
            if n != -1: pre[n] = c
            s[c] = 'O'

    return ''.join(s)