문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다

위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. 이때, 다음과 같은 명령어를 이용하여 표를 편집합니다.

• "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
• "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
• "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
• "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.
  

예를 들어 위 표에서 "D 2"를 수행할 경우 아래 그림의 왼쪽처럼 4행이 선택되며, "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "네오"가 적힌 행을 선택합니다(4행이 삭제되면서 아래 있던 행들이 하나씩 밀려 올라오고, 수정된 표에서 다시 4행을 선택하는 것과 동일합니다).

다음으로 "U 3"을 수행한 다음 "C"를 수행한 후의 표 상태는 아래 그림과 같습니다.

다음으로 "D 4"를 수행한 다음 "C"를 수행한 후의 표 상태는 아래 그림과 같습니다. 5행이 표의 마지막 행 이므로, 이 경우 바로 윗 행을 선택하는 점에 주의합니다.

다음으로 "U 2"를 수행하면 현재 선택된 행은 2행이 됩니다.

위 상태에서 "Z"를 수행할 경우 가장 최근에 제거된 "라이언"이 적힌 행이 원래대로 복구됩니다.

다시한번

"Z"

를 수행하면 그 다음으로 최근에 제거된

"콘"

이 적힌 행이 원래대로 복구됩니다. 이때, 현재 선택된 행은 바뀌지 않는 점에 주의하세요.

이때, 최종 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 "O", 삭제된 행은 "X"로 표시하면 다음과 같습니다.

처음 표의 행 개수를 나타내는 정수 n, 처음에 선택된 행의 위치를 나타내는 정수 k, 수행한 명령어들이 담긴 문자열 배열 cmd가 매개변수로 주어질 때, 모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O, 삭제된 행은 X로 표시하여 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 5 ≤ n ≤ 1,000,000
• 0 ≤ k < n
• 1 ≤ cmd의 원소 개수 ≤ 200,000
  • cmd의 각 원소는 "U X", "D X", "C", "Z" 중 하나입니다.
  • X는 1 이상 300,000 이하인 자연수이며 0으로 시작하지 않습니다.
  • X가 나타내는 자연수에 ',' 는 주어지지 않습니다. 예를 들어 123,456의 경우 123456으로 주어집니다.
  • cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다.
  • 표의 모든 행을 제거하여, 행이 하나도 남지 않는 경우는 입력으로 주어지지 않습니다.
  • 본문에서 각 행이 제거되고 복구되는 과정을 보다 자연스럽게 보이기 위해 "이름" 열을 사용하였으나, "이름"열의 내용이 실제 문제를 푸는 과정에 필요하지는 않습니다. "이름"열에는 서로 다른 이름들이 중복없이 채워져 있다고 가정하고 문제를 해결해 주세요.
• 표의 범위를 벗어나는 이동은 입력으로 주어지지 않습니다.
• 원래대로 복구할 행이 없을 때(즉, 삭제된 행이 없을 때) "Z"가 명령어로 주어지는 경우는 없습니다.
• 정답은 표의 0행부터 n - 1행까지에 해당되는 O, X를 순서대로 이어붙인 문자열 형태로 return 해주세요.

정확성 테스트 케이스 제한 사항

• 5 ≤ n ≤ 1,000
• 1 ≤ cmd의 원소 개수 ≤ 1,000

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

---

전체 코드

from collections import deque

class Node:
    def __init__(self,number):
        self.prev=None
        self.next=None
        self.data=number
        
    def __repr__(self):
        return "data : "+str(self.data)
    
class Linked_list:
    def __init__(self):
        self.head=Node('head')
        self.tail=Node('tail')
        #가장 최근에 놓은 노드를 가리키는 포인터
        self.latest=None
        #현재 커서를 나타내는 포인터
        self.cursor=None
        #복구용 스택
        self.stack=deque()
    
    #'순서대로 뒤를 이어' 삽입 하는 메서드
    def insert(self,node):
        #맨 처음 노드를 넣을 경우
        if self.head.next==None:
            self.head.next=node

            node.prev=self.head
            node.next=self.tail
            
            self.tail.prev=node.next
            
            self.latest=node
        #그외의 경우로 노드를 넣을 때
        else:
            self.latest.next=node
            
            node.prev=self.latest
            node.next=self.tail
            
            self.tail.prev=node.next
            
            self.latest=node
            
    #첫 커서 위치 세팅 메서드
    def set_cursor(self,node):
        self.cursor=node
        
    def down(self,count):
        current=self.cursor
        for i in range(count):
            if current.next==self.tail:
                break
            current=current.next
        self.cursor=current
    
    def up(self,count):
        current=self.cursor
        for i in range(count):
            if current==self.head:
                break
            current=current.prev
        self.cursor=current
    
    def remove(self):
        #삭제할 노드
        removal=self.cursor
        
        #맨 앞 노드일 경우
        if self.cursor.prev==self.head:
            #지워야 할 노드 바로 다음의 노드인 next_node의 포인터 조정
            next_node=self.cursor.next
            next_node.prev=self.head
            self.head.next=next_node
            
            #커서 위치 조정
            self.cursor=next_node
            
        #맨 뒤 노드일 경우
        elif self.cursor.next==self.tail:
            #지워야 할 노드 바로 이전의 노드인 prev_node의 포인터 조정
            prev_node=self.cursor.prev
            prev_node.next=self.tail
            self.tail.prev=prev_node.next
            
            #커서 위치 조정
            self.cursor=prev_node
            
        #중간 노드일 경우
        else:
            prev_node=self.cursor.prev
            next_node=self.cursor.next
            
            prev_node.next=next_node
            next_node.prev=prev_node
            
            self.cursor=next_node
        
        #휴지통 스택에 지운 노드를 담는다.
        self.stack.append(removal)
        
    def undo(self):
        #삭제된 것 중, 가장 최근에 삭제된 것 꺼내기
        poped=self.stack.pop()
        
        #가장 처음 노드였었다면,
        if poped.prev==self.head:
            next_node=poped.next
            next_node.prev=poped
            self.head.next=poped
        #가장 마지막 노드였었다면,
        elif poped.next==self.tail:
            prev_node=poped.prev
            prev_node.next=poped
            self.tail.prev=poped.next
        #중간 노드였었다면,
        else:
            next_node=poped.next
            prev_node=poped.prev
            
            next_node.prev=poped
            prev_node.next=poped
        
    def get_answer(self,number):
        strings=['X']*number
        
        current=self.head.next
        while current!=self.tail:
            strings[current.data]='O'
            current=current.next
            
        return ''.join(strings)

def solution(n, k, cmd):
    answer = ''
    
    linked_list=Linked_list()
    
    
    for i in range(n):
        node=Node(i)
        linked_list.insert(node)
        if i==k:
            linked_list.set_cursor(node)
    
    for i,c in enumerate(cmd):
        split=c.split(' ')
        if len(split)==2:
            if split[0]=='D':
                linked_list.down(int(split[1]))
            else:
                linked_list.up(int(split[1]))
        else:
            if split[0]=='C':
                linked_list.remove()
            else:
                linked_list.undo()
                
    
    answer=linked_list.get_answer(n)
    
    return answer

---

해설

1.효율적인 데이터 구조를 사용해야 한다.

문제의 조건은 다음과 같다.

5 ≤ n ≤ 1,000,000

1 ≤ cmd의 원소 개수 ≤ 200,000

딱봐도 상당히 원소의 개수가 많다.

단순히 배열(파이썬의 리스트)로 풀면 시간 복잡도가 초과될 것이다. 왜냐하면 배열을 실제로 삭제하는 것은 삭제 뿐만 아니라 배열의 원소들을 앞으로 땡기는 것까지 포함되기 때문이다. (O(n))

삽입 역시 마찬가지 원리로 O(n)이 걸린다. (중간에 삽입시, 그 이후의 원소들을 뒤로 떙겨야 한다.)

그리고 이 문제에서 "복구"는 원소 삽입 처리를 해야 한다.

따라서 단순 배열은 효율상 사용할 수 없고, 대신에 이중 연결 리스트를 만들어 사용해야 한다.

이중 연결리스트는 현재 노드에서 다음 노드로 가는 포인터와 이전 노드로 가는 포인터를 갖고 있는 자료구조다.
삽입, 삭제시에 노드들의 포인터만 바꾸면 되므로 O(1)의 시간 복잡도를 갖는다.

이중 연결리스트는 class 문법으로 만들수도 있지만, 더 간단한 방법은 dict를 이용하여 구현하는 것이다.
예를 들면 linked_list[현재 노드 번호]=[이전 노드 번호, 다음 노드 번호]식으로 만든다.

이렇게 하면 노드 포인터처럼 사용할 수 있다. 단, 맨 앞 노드의 이전 포인터와 맨 뒷 노드의 다음 포인터는 null처리같은 것을 해야 한다.

    #딕셔너리로 링크드 리스트 구현
    linked_list=dict()
    for i in range(n):
        #i번 노드는 i+1번으로 가는 next 포인터를 갖고 있다.
        #그리고 i-1번으로 가는 prve 포인터를 갖고 있다. (prev,next)
        linked_list[i]=[i-1,i+1]
        
    #헤드 포인터
    linked_list[0][0]=INF
    #테일 포인터
    linked_list[n-1][1]=INF

2. 삭제를 구현한다.

가장 맨 앞 노드 또는 가장 맨뒤 노드인 경우 NULL처리를 조심해서 구현해야 한다. (if ...≠INF식으로 가드 처리하였다.)

그 외에 일반적인 노드인 경우에는 그 노드의 이전 노드의 다음 포인터를 다음 노드로 가리키게 하고, 그 노드의 다음 노드의 이전 포인터를 이전 노드로 가리키게 한다.

def remove(select,linked_list,arr,undo_stack):
    global INF
    
    #삭제했다고 처리
    arr[select][1]=False
    
    #현재 노드
    current=select
    #(이전 노드, 다음 노드)
    prev_num,next_num=linked_list[current]
    
    #가장 마지막 행인 경우
    if prev_num!=INF and next_num==INF:
        
        #(이전 노드, 현재 노드,다음 노드)형태로 복구 스택에 담기
        #단, 다음 노드는 없으므로 더미로 처리.
        undo_stack.append((prev_num,current,INF))
        
        linked_list[prev_num][1]=INF
    
        #위로 1칸 이동한 값 리턴
        return move_up(1,select,linked_list)
    else:
        #(이전 노드, 현재 노드,다음 노드)형태로 복구 스택에 담기 
        undo_stack.append((prev_num,current,next_num))
        
        #이전 노드는 현재 노드의 다음 노드를 가리키게 됨.
        if prev_num!=INF:
            linked_list[prev_num][1]=next_num
        #다음 노드는 현재 노드의 이전 노드를 가리키게 됨.
        linked_list[next_num][0]=prev_num
        
        #아래로 1칸 이동한 값 리턴
        return move_down(1,select,linked_list)

3.위 아래로 움직이는 것을 구현한다.

삭제 구현에서 포인터 처리를 했기 때문에, 위 아래로 움직이는 것은 포인터를 따라 움직이기만 하면 된다.
단, 선택한 것이 NULL이 되지 않도록 예외 처리해주었다.

def move_down(number,select,linked_list):
    current=select
    for i in range(number):
        next_number=linked_list[current][1]
        
        if next_number==INF:
            return current
            
        current=next_number
    
    return current

def move_up(number,select,linked_list):
    current=select
    for i in range(number):
        prev_number=linked_list[current][0]
        
        if prev_number==INF:
            return current
            
        current=prev_number
        
    return current

4.복구를 구현한다.

삭제할 때 스택에 (이전 노드, 현재 노드, 다음 노드)형태로 담아주었다.
단, 마지막 노드였을 때에는 NULL처리를 해주었으므로 조심해야 한다.

어쨋든 복구할 때는 스택을 POP한 후, 그 튜플 정보에 따라 이전 노드의 다음 포인터와 다음 노드의 이전 포인터가 현재 노드를 가리키도록 변경하면 된다.

def undo(linked_list,arr,undo_stack):
    #(이전 노드, 현재 노드,다음 노드)
    prev_num,current,next_num=undo_stack.pop()
    #복구 처리
    arr[current][1]=True
    #이전 노드의 다음 포인터 갱신
    if prev_num!=INF:
        linked_list[prev_num][1]=current
    
    #가장 마지막행 복구가 아니라면, 다음 노드의 이전 포인터도 갱신한다.
    if next_num!=INF:
        linked_list[next_num][0]=current

링크드 리스트로 구현하기

from collections import deque


# 이중 연결 리스트이므로 next와 previous 모두 있어야 한다.
class Node:
    def __init__(self, value):
        self.val = value
        self.next = None
        self.prev = None


class List:
    def __init__(self, n: int, k: int):
        self.head = Node('start')
        self.tail = Node('end')

        self.cursor = None
        # 가장 최근 행 복구용 스택
        self.stack = deque()

        self.make_list(n)
        self.init_cursor(k)

    # n개의 노드를 가진 이중 연결 리스트 만들기
    def make_list(self, n: int):

        # 첫 번째 노드 세팅하기
        current = Node(0)
        current.prev = self.head
        self.head.next = current

        previous = current

        # 그 이후 노드들 세팅하기
        for i in range(1, n):
            current = Node(i)
            current.prev = previous
            previous.next = current
            previous = current

        # 마지막 노드의 next는 tail이다.
        previous.next = self.tail
        self.tail.prev = previous

    # k번째로 첫 커서 옮기기
    def init_cursor(self, k: int):
        self.cursor = self.head.next

        for _ in range(k):
            self.cursor = self.cursor.next

    def up_cursor(self, move_count: int):

        for _ in range(move_count):
            if self.cursor.prev:
                self.cursor = self.cursor.prev

    def down_cursor(self, move_count: int):

        for _ in range(move_count):
            if self.cursor.next:
                self.cursor = self.cursor.next

    def delete_current(self):
        current = self.cursor
        # 삭제할 게 가장 마지막이면, 바로 윗행 선택
        if current.next == self.tail:
            self.cursor = current.prev
        # 아니라면, 바로 아래행 선택
        else:
            self.cursor = current.next

        # 지워야 할 게 맨 앞이였던 거라면, 예외 처리
        if current == self.head:
            self.head.next = self.cursor
            self.cursor.prev = self.head
        # 지워야할 게 맨 뒤라면, 예외 처리
        elif current.next == self.tail:
            self.cursor.next = self.tail
            self.tail.prev = self.cursor
        else:
            current.prev.next = self.cursor
            self.cursor.prev = current.prev

        # 최근에 삭제한 행을 복구용 스택에 집어 넣기 (next, prev 포인터는 기존 연결된 노드들을 가리키고는 있다.)
        self.stack.append(current)

    # 최근에 삭제한 것 스택에서 뽑아내서 다시 복구하기
    def restore(self):
        latest = self.stack.pop()
        if latest.prev == self.head:
            self.head.next.prev = latest
            self.head.next = latest
        elif latest.next == self.tail:
            self.tail.prev.next = latest
            self.tail.prev = latest
        else:
            latest.prev.next = latest
            latest.next.prev = latest

    def print_list(self, n: int):
        arr = ['X'] * n

        current = self.head.next

        while current != self.tail:
            arr[current.val] = 'O'
            current = current.next

        return ''.join(arr)


def solution(n, k, cmd):
    double_list = List(n, k)

    for command in cmd:
        if command == 'C':
            double_list.delete_current()
        elif command == 'Z':
            double_list.restore()
        else:
            split = command.split(' ')
            if split[0] == 'U':
                double_list.up_cursor(int(split[1]))
            else:
                double_list.down_cursor(int(split[1]))
    

    answer = double_list.print_list(n)

    return answer

테스트 케이스

각각 n,k,cmd, 결과를 나타낸다.

4 0 ["C"] ["XOOO"]
4 0 ["C","C","C"] ["XXXO"]
4 0 ["C", "C", "Z"] ["XOOO"]
4 3 ["C"] ["OOOX"]
4 3 ["C","C","C"] ["OXXX"]
4 3 ["C","C","Z"] ["OOOX"]