[문제풀이] 표 편집

About this offer

문제 표 편집 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다. 위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행 을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(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 \leq$ n $\leq 1,000,000$ $0 \leq$ k $<$ n $1 \leq$ cmd 의 원소 개수 $\leq 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 \leq$ n $\leq 1,000$ $1 \leq$ cmd 의 원소 개수 $\leq 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" 문제 풀이 배열은 데이터를 중간에 삽입/삭제하면 효율이 좋지 못함. [0, 1, 2, 3, 4, 5, 6, 7] "D 2" k 가 2이므로 2에서 아래로 2칸 내려간다. 2 $\rightarrow$ 3 $\rightarrow$ 4 현재 값은 4이다. "C" 삭제 작업을 수행한다. [0, 1, 2, 3, 5, 6, 7] 4는 되돌릴 수 있어야 하므로 스택에 별도로 저장한다. [4] 4가 삭제되고 기준 값은 5가 된다. "U 3" 기준 값이 5이므로 위로 3칸 올라가야 한다. 5 $\rightarrow$ 3 $\rightarrow$ 2 $\rightarrow$ 1 현재 값은 1이다. "C" 삭제 작업을 수행한다. [0, 2, 3, 5, 6, 7] 1은 되돌릴 수 있어야 하므로 스택에 별도로 저장한다. [4, 1] 1이 삭제되고 기준 값은 2가 된다. "D 4" 기준 값이 2이므로 아래로 4칸 내려가야 한다. 2 $\rightarrow$ 3 $\rightarrow$ 5 $\rightarrow$ 6 $\rightarrow$ 7 현재 값은 7이 된다. "C" 삭제 작업을 수행한다. [0, 2, 3, 5, 6] 7은 되돌릴 수 있어야 하므로 스택에 별도로 저장한다. [4, 1, 7] 7이 삭제되었는데 7은 제일 밑의 표이므로 제일 밑의 표는 아래가 아니라 위로 올라가야 한다. 따라서 기준 값은 6이 된다. "U 2" 기준 값이 6이므로 위로 2칸 올라가야 한다. 6 $\rightarrow$ 5 $\rightarrow$ 3 현재 값은 3이다. "Z" 삭제된 표들을 보관한 스택에서 제일 위에 있는(제일 마지막에 넣은) 표를 꺼내서 다시 표에 넣는다. 근데, 그 값과 이전, 이후 값을 기억하고 있어야 넣을 수 있다. "7은 (이전: 6, 이후: X)" 이므로 나중에 구현할 때는 이전, 이후 값도 같이 기억하도록 해야겠다. 아무튼, 표는 아래와 같이 된다. [0, 2, 3, 5, 6, 7] 삭제 스택 [4, 1] "Z" 다시 한 번 되돌리므로 1을 복귀해준다. [0, 1, 2, 3, 5, 6, 7] [4] 이런 과정을 거쳐야 한다. 우선 전체적인 흐름은 다음과 같다. cmd 에 있는 명령어를 수행하고 삭제 스택에 있는 요소를 꺼내서 그 값이 있는 것들은 X 표시를 해서 나중에 반환하면 되는데 join 명령어를 활용해서 반환하면 될 것 같다. 그렇게 되면 배열로 관리할 수 있을 것이다. 인덱스 0 1 2 3 4 5 6 7 O O O O O O O O 이렇게 초기값을 넣어두고 삭제 스택에서 하나씩 빼면서 해당 값에 해당하는 인덱스는 X로 변경 현재 4가 삭제되어있으므로 인덱스 0 1 2 3 4 5 6 7 O O O O X O O O 이렇게 하고 join 을 이용해서 문자열로 바꿔서 반환하면 될 것이다. def solution(n, k, cmd): deleted = [] result = ["O"] * n up = [i - 1 for i in range(n)] down = [i + 1 for i in range(n)] down[-1] = -1 for c in cmd: if c == "C": up_node, down_node = up[k], down[k] deleted.append((k, up_node, down_node)) if up_node != -1: down[up_node] = down_node if down_node != -1: up[down_node] = up_node k = down_node if down_node != -1 else up_node elif c == "Z": node, up_node, down_node = deleted.pop() if up_node != -1: down[up_node] = node if down_node != -1: up[down_node] = node else: move, num = c.split() if move == "U": for _ in range(int(num)): k = up[k] else: for _ in range(int(num)): k = down[k] for node, _, _ in deleted: result[node] = "X" return "".join(result) 느낀점 어떻게 문제를 풀어야 할지 감을 잡지 못해서 제미나이에게 접근법을 물어보고 풀이를 해봤다. 파이썬 기본 리스트( list )의 함정 이건 중간 삽입/삭제 효율이 좋지 못하다는 것. 이미 알고 있었던 것이니 패스 "Z" 명령어를 위한 자료 구조 가장 마지막에 들어온 데이터부터 순서대로 꺼내야 하는 자료 구조를 쓰라는 것. 이미 스택을 쓰고자 생각하고 있었으므로 패스 결국 나의 문제는 어떤 스택을 써야 하는지는 알고 있는데 어떤 아이디어로 구현을 할지가 부족하다는 점이었다. 이 부분을 앞으로 생각하면서 구현을 할 수 있도록 노력해야 할 것 같다. [-1] 인덱싱 파이썬에서 [-1] 인덱싱은 마지막 원소 접근 기능이 작동하는 것을 막기 위한 비어있음(Null)을 나타내는 기호이다. 배열 기반으로 연결 리스트를 만들 때, 이전, 다음 노드가 없다는 의미( Null 이나 None )를 숫자로 표현하기 위해 보통 -1 을 사용한다.