[스택, linked list] 프로그래머스 - 표 편집

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

문제 설명 :

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

위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(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

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

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

---

입출력 예

n	k	cmd	result
8	2	["D 2","C","U 3","C","D 4","C","U 2","Z","Z"]	"OOOOXOOO"
8	2	["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"]	"OOXOXOOO"

---

문제 풀이:

linked list와 stack을 이용하면 풀 수 있는 문제였다. 초반에 linked list 사용하는 것에 대해 고민을 많이 했는데, Node라는 클래스를 별도로 만들어서 사용할 수도 있었지만, 풀이를 찾아보니 딕셔너리 형태를 이용해서도 쉽게 만드신 분이 있었다. 그래서 나도 그 풀이를 따라해보고자 딕셔너리 형태로 제작했다. 딕셔너리 형태로 linked list를 만들면 기존 linked list가 처음과 끝이 아닌, 가운데에 있는 노드를 바로 호출하기 어렵다(시간이 오래 걸린다)는 단점까지 극복할 수 있었다. 

 

0번째 노드와 마지막 노드는 None을 가리키고 있어야 하는 부분이 있어서 별도로 초기화를 해주었다. C인 경우는 k의 값에 X를 쳐주고, 삭제 처리 (노드 k-1에 k의 after값을 연결, 노드 k+1에  k의 before값을 연결) 해준다. 그리고 삭제된 k (그리고 k의 before, after 값도)를 스택에 넣어 ctrl-z 누르면 복원할 수 있도록 해준다. 그리고 나면 k를 한 칸 아래로 이동해주는데, k가 마지막 값이었던 경우는 한 칸 위로 이동해준다. 

 

'Z'인 경우를 살짝 고민했는데, 그대로 stack에서 꺼낸 before과 after 사이에 연결하면 되었다. a라는 수가 pop되기 전에 a의 before과 after도 사라진 상태이면 어쩌나 고민했지만, 가장 최근에 삭제되었던 것부터 복원이 되기 때문에 before과 after이 사라졌더라도 a의 before과 after이 a보다 먼저 복원된다는 점에서 고민할 필요가 없었다. 

 

그 외의 명령어 ('U'나 'D') 도 문제를 잘 읽고 그대로 해결해주면 된다. 나는 사실 초반에 현재 위치가 가장 첫 번째 줄일 때 U 3이 나오면 가장 마지막 줄로 이동해서 2칸 더 올라가는 줄 알고 그렇게 풀었는데 (circular queue나 list 정도로 생각했다) 문제를 다시 읽어보니 그럴 필요가 없는 것이었다. 문제가 길기 때문에 더 집중해서 놓치는 조건이 없는 것이 중요했던 것 같다. 

def solution(n, k, cmd):
    answer = ['O'] * n
    nodes = {i : [i-1, i+1] for i in range(n)}
    nodes[0] = [None, 1]
    nodes[n-1] = [n-2, None]
    stack = []
    
    for c in cmd:
        if c.startswith("C"):
            answer[k] = 'X'
            before, after = nodes[k]
            if before != None:
                nodes[before][1] = nodes[k][1]
            if after != None:
                nodes[after][0] = nodes[k][0]

            stack.append([before,k, after])
            k = nodes[k][0] if nodes[k][1] == None else nodes[k][1]
                
        elif c.startswith("Z"):
            before, z, after = stack.pop()
            answer[z] = 'O'
            if after != None:
                nodes[after][0] = z
            if before != None:
                nodes[before][1] = z

        else:   
            command, idx = c.split()
            idx = int(idx)
            if command == 'D':
                while idx != 0 and nodes[k][1] != None:
                    idx -= 1
                    k = nodes[k][1]

            else:
                while idx != 0 and nodes[k][0] != None:
                    idx -= 1
                    k = nodes[k][0]

        
    final = ''        
    for elem in answer:
        final += elem
    return final