[프로그래머스] 표 편집 (2021 카카오 인턴십) / JavaScript
표 편집
https://programmers.co.kr/learn/courses/30/lessons/81303
코딩테스트 연습 - 표 편집
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"
programmers.co.kr
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다
위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(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 해주세요.
풀이
function solution(n, k, cmd) {
const Node = function (index, prev) {
this.index = index;
this.prev = prev;
this.next = null;
};
let prevNode = new Node(0);
let select; //선택된 노드
// 링크드리스트 생성
for (let i = 1; i < n; i++) {
const cntNode = new Node(i, prevNode);
prevNode.next = cntNode;
prevNode = cntNode;
// 처음 선택된 노드 저장
if (i === k) {
select = cntNode;
}
}
let trashBin = [];
const moveSelectedNode = (count, direction) => {
for (let i = 0; i < count; i++) {
if (!select[direction]) break;
select = select[direction];
}
};
const deleteNode = () => {
const prev = select.prev;
const next = select.next;
trashBin.push(select);
select = next ? next : prev;
if (prev) prev.next = next;
if (next) next.prev = prev;
};
const recoverNode = () => {
const targetNode = trashBin.pop();
const prev = targetNode.prev;
const next = targetNode.next;
if (prev) prev.next = targetNode;
if (next) next.prev = targetNode;
};
cmd.forEach((c) => {
switch (c[0]) {
case "U":
moveSelectedNode(c.split(" ")[1], "prev");
break;
case "D":
moveSelectedNode(c.split(" ")[1], "next");
break;
case "C":
deleteNode();
break;
case "Z":
recoverNode();
break;
}
});
let result = Array(n).fill("O");
trashBin.forEach((node) => {
result[node.index] = "X";
});
return result.join("");
}
링크드 리스트를 사용하여 해결하였다.
5 ≤ n ≤ 1,000,000 이며 1 ≤ cmd의 원소 개수 ≤ 200,000 이므로 일반 배열로 풀면 효율성 테스트를 통과하지 못한다.
제일 까다로운 조건은 Z 인데, 삭제된 노드를 되돌리기 위해서는 노드가 원래 있었던 자리를 기억하고 있어야 한다.
위 그림과 같이 링크드리스트를 사용하여 각 노드는 앞, 뒤 노드에 대한 정보를 포함하도록 설계해주었다. 그러면 삭제했던 노드를 되돌릴 때 제자리를 쉽게 찾을 수 있다.
const Node = function (index, prev) {
this.index = index;
this.prev = prev;
this.next = null;
};
let prevNode = new Node(0);
let select; //선택된 노드
// 링크드리스트 생성
for (let i = 1; i < n; i++) {
const cntNode = new Node(i, prevNode);
prevNode.next = cntNode;
prevNode = cntNode;
// 처음 선택된 노드 저장
if (i === k) {
select = cntNode;
}
}n만큼을 반복하면서 링크드리스트를 생성해준다. prevNode에 index 0을 가지는 노드를 넣고 시작하며, 노드를 생성하면 prevNode의 next에 생성한 노드를 연결해주고 prevNode값을 변경한다.
처음 선택된 행(k)의 노드는 select에 넣어준다.
U, D
선택된 노드에서 X 번만 링크를 따라가면 된다.
const moveSelectedNode = (count, direction) => {
for (let i = 0; i < count; i++) {
if (!select[direction]) break;
select = select[direction];
}
};X 값을 count로 받아서 count만큼 이동한다. U 일때는 direction 에 "prev" 가 들어가고, D 일때는 "next"가 들어간다.
count번만 이동하면 되므로 시간복잡도 O(X) 이다.
C
선택한 노드를 trashBin에 넣어주고 양 옆의 노드들 링크 정보를 변경해준다.
const deleteNode = () => {
const prev = select.prev;
const next = select.next;
trashBin.push(select);
select = next ? next : prev;
if (prev) prev.next = next;
if (next) next.prev = prev;
};이때 만약 삭제 할 노드의 다음 칸이 null 이라면 prev 를 선택해야 한다는 점을 잊지 말아야한다.
select 에 담긴 노드 정보를 변경해주면 되기 때문에 시간복잡도 O(1)이다.
Z
trashBin에 담긴 노드를 복구해준다.
const recoverNode = () => {
const targetNode = trashBin.pop();
const prev = targetNode.prev;
const next = targetNode.next;
if (prev) prev.next = targetNode;
if (next) next.prev = targetNode;
};가장 최근에 삭제한 순서로 되돌리기 때문에 trashBin.pop() 을 해준다.
trashBin에서 꺼낸 노드의 링크 정보를 보고 원래 자리로 다시 연결한다. 이때 시간복잡도는 O(1)이다.
cmd.forEach((c) => {
switch (c[0]) {
case "U":
moveSelectedNode(c.split(" ")[1], "prev");
break;
case "D":
moveSelectedNode(c.split(" ")[1], "next");
break;
case "C":
deleteNode();
break;
case "Z":
recoverNode();
break;
}
});switch문을 사용하여 각각의 명령어에 따른 함수를 실행해주었다.
let result = Array(n).fill("O");
trashBin.forEach((node) => {
result[node.index] = "X";
});O 가 담긴 배열을 만들고 trashBin 에 있는 노드의index는 X로 바꿔준다.
return result.join("");배열을 문자열로 바꿔서 return해준다.