[Programmers] Lv3. 표 편집

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

문제설명

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

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

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

제한사항

• 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

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

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

문제해설

처음에 풀 때, Z가 삭제된 위치에 복구하는지 표의 마지막 인덱스에 복구하는지 제대로 확인하지 못해 헤맸던 문제다. 

만약 마지막 인덱스에 복구가 된다면 난이도가 매우 쉬워지지만, 삭제했던 인덱스에 복구하기 때문에 난이도가 많이 올라간다.

인덱스를 삭제하거나 복구할 때, 인덱스를 다루는 방법은 두 가지가 있다.

1. 절대적인 인덱스를 부여해서 행 간의 순서 관계를 보존하기(원본 데이터 유지)
2. 원본 표 데이터에서 삭제/복구하면서 상대적인 순서 인덱스를 유지하기

1번의 방법은 표 데이터를 유지한 채, 삭제된 데이터인지만 표시하여 k가 이동할 때 얼마만큼 변할지 정해야하고,

2번의 방법은 k의 이동은 x값 만큼의 연산만으로 이동이 가능하지만 표 데이터를 수정하는 비용이 발생한다.

 

여기서는 Z 복구의 특성때문에, 순서관계를 파악하기 좋은 1번의 접근방법을 사용한다.

 

첫번째로, Z를 구현하는 가장 쉬운 방법은 delete된 데이터를 저장하는 stack을 사용하면 된다. 

삭제된 인덱스를 stack에 저장한 뒤, pop만 해주면 쉽게 삭제된 데이터를 복구할 수 있다.

대신, index를 가리키는 k가 어떻게 이동할 지 잘 구현해야 한다.

제한사항에서는 U와D의 X의 합이 100,0000이 되기 때문에 한칸씩 움직이는 방법은 시간초과가 날 것이라 생각했다.

결론만 말하자면 연결리스트 자료구조를 사용해도 시간초과가 나지 않는다. 

 

연결리스트를 사용하기로 했으니, 각 인덱스에서 왼쪽과 오른쪽을 가리키는 형태의 연결리스트를 구현한다.

가장 왼쪽 인덱스의 왼쪽과 가장 오른쪽 인덱스의 오른쪽을 None으로 설정해서 리스트의 끝을 알린다.

    next_link = [[i-1,i+1] for i in range(n)]
    next_link[0][0]=None
    next_link[-1][1] = None

 

 

이렇게 구성된 연결리스트는 U와D에 대해서 X번의 연산으로 이동이 가능하다. 범위를 벗어나는 입력은 주어지지 않으니 간단하게 구현해도 된다.

if c[0] == 'D' or c[0] == 'U':
    c,x = c.split()
if c == 'D':
    for _ in range(int(x)):
        k = next_link[k][1]
elif c == 'U':
    for _ in range(int(x)):
        k = next_link[k][0]

 

C에 대해서는 K가 가리키는 인덱스를 제거한 뒤 del_list라는 stack에 저장한다.

그리고 해당 인덱스의 왼쪽과 오른쪽을 이어준다.

k는 리스트의 끝일 경우 왼쪽으로, 아니면 오른쪽으로 이동하면 된다.

elif c == 'C':
    del_list.append(k)
    if next_link[k][0] != None:
        next_link[next_link[k][0]][1] = next_link[k][1]
    if next_link[k][1] != None:
        next_link[next_link[k][1]][0] = next_link[k][0]
    if next_link[k][1] == None:
        k = next_link[k][0]
    else:
        k = next_link[k][1]

 

Z에서는 del_list에서 pop을 해서 가장 최근에 삭제된 인덱스를 불러온 뒤, 연결을 복구해주기만 하면 된다.

삭제된 인덱스에서는 기존의 연결관계를 기억하고 있고, 가장 최근에 삭제된 순서대로 복구하기 떄문에 원래의 형태로 복구 되는 것이 보장된다.

추가로 복구할 때, 왼쪽과 오른쪽이 있는지만 확인하는 예외처리만 하면 된다.

elif c == 'Z':
    t = del_list.pop()
    if next_link[t][0] != None:
        next_link[next_link[t][0]][1] = t
    if next_link[t][1] != None:
        next_link[next_link[t][1]][0] = t

 

마지막에 답은 del_list에 저장된 index에 따라서 X표시만 해주면 된다.

    answer = ['O' for _ in range(n)]
    for d in del_list:
        answer[d]='X'

 

최종 코드

#D x=현재 x칸아래 선택
#U x=현재 x칸 위 선택
#C = 현재삭제 및 아래 선택, 마지막행인경우 위 선택
#Z = 최근삭제 복구

def solution(n, k, cmd):
    answer = ['O' for _ in range(n)]
    next_link = [[i-1,i+1] for i in range(n)]
    next_link[0][0]=None
    next_link[-1][1] = None
    del_list = []
    for c in cmd:
        if c[0] == 'D' or c[0] == 'U':
            c,x = c.split()
        if c == 'D':
            for _ in range(int(x)):
                k = next_link[k][1]
        elif c == 'U':
            for _ in range(int(x)):
                k = next_link[k][0]
        elif c == 'C':
            del_list.append(k)
            if next_link[k][0] != None:
                next_link[next_link[k][0]][1] = next_link[k][1]
            if next_link[k][1] != None:
                next_link[next_link[k][1]][0] = next_link[k][0]
            if next_link[k][1] == None:
                k = next_link[k][0]
            else:
                k = next_link[k][1]
        elif c == 'Z':
            t = del_list.pop()
            if next_link[t][0] != None:
                next_link[next_link[t][0]][1] = t
            if next_link[t][1] != None:
                next_link[next_link[t][1]][0] = t
                
    for d in del_list:
        answer[d]='X'
    
    
    return "".join(answer)

 

추가 아이디어

이 문제에서는 시간을 넉넉하게 준 것인지 X총합이 100만이 안되는 것인지 연결리스트로 구현해도 시간초과가 나지 않았다.

연결리스트의 문제는 탐색에 인덱스가 떨어진 거리만큼의 O(n)의 시간이 들기 때문에 느리다는 것이다.

이를 해결하기 위해서 트리의 형태로 탐색을 O(log n)으로 줄여줄 수 있다.

트리 중에서도 각 구간의 합을 저장하는 세그먼트 트리가 있다.

기존 data 와 같은 크기로 리스트를 생성하고 1로 채운다.

그 다음 그 리스트의 위로 세그먼트 트리를 생성하면 트리는 각 구간에 몇 개의 데이터가 있는지 표현하게 된다.

x만큼의 이동을 위해서 leaf node에서 부모를 따라 올라갈 때, 자신이 left child인지 right child인지 알 수 있다면 X의 값이 얼마던 트리의 높이만큼의 탐색시간안에 이동이 가능해진다.

세그먼트 트리를 완전 이진 트리로 구현했다면, 부모로 이동할 때, 자신이 어느 child에서 왔는지 알 수 있다.

 

만약 삭제가 이루어질 경우, k index 위치의 값을 0으로 바꾸고 root까지 따라 올라가며 값을 1씩 빼주면 된다.

복구도 위와 같이 복구할 index 위치의 값을 1로 바꾸고 root까지 1씩 더해주면 된다.