[카카오 기출] 표 편집

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

코딩테스트 연습 - 표 편집

 

def solution(n, k, cmd):
    table = ["O"]*n
    cur = k
    trash = []
    
    next_dct = {}
    for i in range(n-1):
        next_dct[i] = i+1
    next_dct[n-1] = -1
    next_dct[-1] = -1
    
    pre_dct = {}
    for i in range(n):
        pre_dct[i] = i-1
    pre_dct[-1] = -1
    
    for i in range(len(cmd)):     
        command = cmd[i]
        if command == 'C':  # delete
            # push to trash and update value
            trash.append(cur)
            table[cur] = 'X'
            
            # update dct
            pre = pre_dct[cur]
            next = next_dct[cur]
            pre_dct[next] = pre
            next_dct[pre] = next
            
            # cursor move
            if next == -1 : # last
                cur = pre
            else:
                cur = next
                                                 
        elif command == 'Z':
            # load again
            revived = trash.pop()
            table[revived] = 'O'
            
            # dct update
            pre = pre_dct[revived]
            next = next_dct[revived]
            pre_dct[next] = revived
            next_dct[pre] = revived
            
        elif command[0] == 'U':
            for i in range(int(command[2:])):
                cur = pre_dct[cur]
        elif command[0] == 'D':
            for i in range(int(command[2:])):
                cur = next_dct[cur]
    
    return "".join(table)

코테때는 효율성을 통과하지 못하여 다시 풀어보았다.

딕셔너리를 사용하여 이전, 넥스트 인덱스를 저장해놓는 식으로 하니 효율성을 통과할 수 있었다.

 

근데 막판에 엄청난 삽질로 원인을 찾지도 못하고 1시간을 날렸는데

command가 U 또는 D인 경우 반복문 안의 범위를

range(int(command[2:])) 가 아닌 range(int(command[2]))로 적는 바람에... 많은 시간을 소비했다.

숫자가 두자리 이상인 경우를 생각하지 않은 것이다. 이런 사소한 실수는 실전에서 절대 하면 안된다.

 

++ undo의 과정에서 환생한 노드를 다시 연결리스트에 연결시켜줘야 하는데,

스택 구조상 가장 최근 삭제된 노드가 복구되는 것이기 때문에 삭제될 당시 연결된 앞, 뒤 노드들은 여전히 삭제가 안된 상태이다. 따라서 바로 연결시켜주면 된다.

 

++ 깔끔하게 이중연결리스트로도 풀어봤다.

class Node:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

class DoubleLinkedList:
    def __init__(self, n, k):
        self.table = ["O" for _ in range(n)]
        self.stack = []
        self.head = Node(-1)
        self.tail = Node(n+1)
        self.head.next = self.tail
        self.tail.prev = self.head

        # make node
        for i in range(n):
            self.__add(i)

        # init pos
        self.cur = self.head
        for _ in range(k + 1):
            self.cur = self.cur.next

    def __add(self, pos):
        new = Node(pos)
        self.tail.prev.next = new
        new.prev = self.tail.prev
        new.next = self.tail
        self.tail.prev = new

    def up(self, x):
        for _ in range(x):
            self.cur = self.cur.prev

    def down(self, x):
        for _ in range(x):
            self.cur = self.cur.next

    def delete(self):
        self.cur.prev.next = self.cur.next
        self.cur.next.prev = self.cur.prev

        self.table[self.cur.val] = "X"
        self.stack.append(self.cur)

        if self.cur.next == self.tail:
            self.cur = self.cur.prev
        else:
            self.cur = self.cur.next

    def undo(self):
        popped = self.stack.pop()
        self.table[popped.val] = "O"
        
        popped.prev.next = popped
        popped.next.prev = popped

    def search(self):
        return ''.join(self.table)


def solution(n, k, cmd):
    dll = DoubleLinkedList(n, k)
    for c in cmd:
        if len(c) >= 3:
            if c[0] == 'U':
                dll.up(int(c[2:]))
            else:
                dll.down(int(c[2:]))
        else:
            if c == 'C':
                dll.delete()
            else:
                dll.undo()

    return dll.search()