14. Edit Table
Sunhyup Lee. (2024). To be a successful candidate for the coding test. goldenrabbit. p.173.
Problem solving
1. LinkedList를 이용한 접근법
linkedList solving
Jay Tak
1. 인덱스만으로 연산하기
cmd의 명령어를 수행할 때마다 해당 행의 위와 아래에 위치한 행의 번호를 계속 업데이트한다.
즉, 실제 배열을 삽입, 삭제 연산을 하는 대신 인접한 행의 정보를 활용한다.
2. 삭제하는 경우
삭제는 다음 세 가지를 고민해야 한다.
1) 삭제된 행을 저장하는 방법
2) 마지막 행이 삭제되었을 때, 바로 위의 행을 선택하는 방법
3) 배열을 삭제하지 않고도 인덱스를 활용해서 삭제가 된 것처럼 만드는 방법
3. 복구하는 경우
복구 동작의 핵심은 기존 삭제 위치에 행을 삽입해야 한다.
1) 스택에서 최근에 삭제한 행을 팝하고, 삭제한 원소를 restore에 보관합니다.
2) 행 번호 restore를 기준으로 윗 행의 다음과 아래행의 이전은 restore가 되어야 합니다. 즉, down[up[restore]]와 up[down[restore]]가 restore여야 합니다.
4. 테이블 양 끝에서 연산하는 경우
테이블 양 끝에서도 추가와 삭제를 할 수 있다. 그러니 앞서 정의한 삭제 연산과 복구 연산은 양 끝에서도 정상 동작해야 한다. 맨 위의 행이 삭제된다고 가정하면 다음 식을 그대로 적용할 수 있어야 한다.
up[down[0]] = up[0]이므로, up[0] - 1
down[up[0]] = down[k]이므로, down[-1] = down[0]
개념상 up, down 배열을 적용해 상대 인덱스를 활용하는 건 좋은 생각이지만, 맨 위의 위는 지금까지 생각한 테이블 상에는 없었습니다. 그래서 식을 적용하자니 이상하다. 그렇다고 이 좋은 생각을 버리기에는 너무 아깝다. 해결책은 간단합니다. 양 끝에서 명령어를 수행할 때도 정상적으로 위 식이 적용되게 가상의 공간을 도입하면 된다.
function solution(n, k, cmd) {
// ➊ 삭제된 행의 인덱스를 저장하는 리스트
const deleted = [];
// ➋ 링크드 리스트에서 각 행 위아래의 행의 인덱스를 저장하는 리스트
const up = [...new Array(n + 2)].map((_, i) => i - 1);
const down = [...new Array(n + 1)].map((_, i) => i + 1);
// ➌ 현재 위치를 나타내는 인덱스
k += 1;
// ➍ 주어진 명령어(cmd) 리스트를 하나씩 처리
for (const item of cmd) {
// ➎ 현재 위치를 삭제하고 그다음 위치로 이동
if (item.startsWith("C")) {
deleted.push(k);
up[down[k]] = up[k];
down[up[k]] = down[k];
k = n < down[k] ? up[k] : down[k];
}
// ➏ 가장 최근에 삭제된 행을 복원
else if (item.startsWith("Z")) {
const restore = deleted.pop();
down[up[restore]] = restore;
up[down[restore]] = restore;
}
// ➐ U 또는 D를 사용해 현재 위치를 위아래로 이동
else {
const [action, num] = item.split(" ");
if (action === "U") {
for (let i = 0; i < num; i++) {
k = up[k];
}
} else {
for (let i = 0; i < num; i++) {
k = down[k];
}
}
}
}
// ➑ 삭제된 행의 위치에 'X'를, 그렇지 않은 행의 위치에 'O'를 포함하는 문자열 반환
const answer = new Array(n).fill("O");
for (const i of deleted) {
answer[i - 1] = "X";
}
return answer.join("");
}