카카오 2021 채용연계형 인턴쉽 코딩테스트 - 표 편집

문제

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

해설

문제를 보면 표를 수정하는 작업을 구현해야한다.

1. 현재 커서를 위 아래로 이동하는 작업
2. 표의 한줄을 삭제하고 커서를 아래로 위치, 삭제하는 표가 맨 아래일 경우 맨 위로 이동
3. 가장 마지막에 삭제한 표를 원래대로 되돌리는 기능

위 세가지를 구현해야한다.

시도한 방법

처음 시도한 방법으로는 표의 위치를 인덱스로 잡고 배열로 해결을 시도해보았다.
1. 표의 한줄을 삭제하는 기능으로 해당 인덱스를 O 에서 X로 바꾸고 아래로 위치
2. 커서를 이동시킬 때는 한칸 위 아래로 이동했을 때 해당 위치가 X일 경우 한 칸 더 이동시킴
3. 가장 마지막에 삭제한 표를 원래대로 되돌리는 기능은 해당 인덱스를 스택에 넣고 하나씩 되돌리는 기능
위 세가지 방법을 구현하여 시도했으나 시간 초과가 나면서 실패했다.

왜 시간 초과가 나는가?

왜 시간초과가 나는지 궁금했다.
여기서 주어지는 표의 범위는 5 <= n <= 1,000,000이다.
위의 방법대로 시도한다면 예상되는 기능들의 시간복잡도는 아래와 같다.
커서를 위 아래로 바꾸는 기능은 바로 위 아래줄이 삭제가 되지 않았다면 O(1)만에 도달할 수 있다. 하지만 전부 삭제되고 마지막에 위치한 표만 남아있다면? O(N)이 소요 될 것이다.

삭제하는 기능 또한 삭제 후 커서를 이동하기 때문에 최악의 경우 O(N)이 소요될 것이다.
그렇다면 기능의 시간은 O(N)보다 더 빠르게 만들어야한다.

해결 방법

위의 시도 방법에서 O(N)이 걸려서 시간 초과가 발생했는데, 위의 방법을 다시 생각해보자
위치를 이동하면 삭제가 아닌 부분을 찾아야해서 시간이 소요된다.
그렇다면 표의 내용이 변동될 때 해당 표에서 다음 표의 위치를 저장하고 저장한 위치대로만 이동하게 된다면 커서 이동이 O(1)이 소요된다.
이전, 다음 위치를 저장하는 방법인 Linked List를 구현한다면 충분히 시간내에 해결이 가능하다.
표의 기능을 연결 리스트로 구현하고, 정답인 부분만 배열로 만들어서 O,X 수정해주면 충분히 정답에 접근할 수 있다.

소스코드

from collections import deque

class node():
    def __init__(self):
        self.idx = 0
        self.prev = 0
        self.next = 0

def make_node_and_checklist(n,k):
    head = 0
    tail = 0
    pos = 0
    check_list = ["O" for i in range(n)]
    for i in range(n):
        if i <= 0:
            head = node()
            head.idx = i
            head.prev = head
            head.next = head
            tail = head
            if head.idx == k:
                pos = head
        elif 0 < i < n-1:
            tmp_node = node()
            tmp_node.idx = i
            tmp_node.prev = tail
            tail.next = tmp_node
            tail = tmp_node

            if tail.idx == k:
                pos = tail

        elif i >= n-1:
            tmp_node = node()
            tmp_node.idx = i
            tmp_node.prev = tail
            tmp_node.next = tmp_node

            tail.next = tmp_node
            tail = tmp_node

            if tail.idx == k:
                pos = tail

    return head,check_list,pos

def move_node(current_node,command,length):
    if command == 'U':
        for idx in range(length):
            current_node = current_node.prev
    else:
        for idx in range(length):
            current_node = current_node.next
    return current_node

def delete_node(current_node:node,undo:deque,n:int,check_list:list):
    prev_node = current_node.prev
    next_node = current_node.next

    undo.append(current_node)
    check_list[current_node.idx] = 'X'

    if current_node.idx == prev_node.idx:
        next_node.prev = next_node
        return next_node
    elif (current_node.idx != prev_node.idx) and (current_node.idx != next_node.idx):
        prev_node.next = next_node
        next_node.prev = prev_node
        return next_node
    else:
        prev_node.next = prev_node
        return prev_node

def restore(restore_node:node,check_list:list,n):
    restore_prev = restore_node.prev
    restore_next = restore_node.next
    check_list[restore_node.idx] = 'O'

    if restore_node.idx == restore_prev.idx:
        restore_next.prev = restore_node
    elif (restore_node.idx != restore_next.idx) and (restore_node.idx != restore_prev.idx):
        restore_prev.next = restore_node
        restore_next.prev = restore_node
    else:
        restore_prev.next = restore_node

def solution(n, k, cmd):
    answer = ''
    undo = deque()
    node_list,check_list,current_node = make_node_and_checklist(n,k)
    for c in cmd:
        command = c.split(' ')
        if command[0] == 'U' or command[0] == 'D':
            current_node = move_node(current_node,command[0],int(command[1]))
        elif command[0] == 'C':
            current_node = delete_node(current_node,undo,n,check_list)
        elif command[0] == 'Z':
            restore_node = undo.pop()
            restore(restore_node,check_list,n)
    answer = ''.join(check_list)
    return answer