Programmers / Level 3 / 표 편집 / JS

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

프로그래머스

 

개요

이번 시간에는 Programmers의 Level 3,

'표 편집' 문제에 대해 알아보겠습니다.

먼저, 문제에 대해 간략히 설명드리고,

제한사항을 살펴본 뒤,

문제를 해결해보면서 마무리하겠습니다.

 

문제

문제에는 총 네 종류의 명령이 주어질 수 있습니다.

 

첫 번째, 'U' 명령을 수행하면, X칸 위에 있는 행을 선택합니다.

두 번째, 'D' 명령을 수행하면, X칸 아래에 있는 행을 선택합니다.

세 번째, 'C' 명령을 수행하면, 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다.

단, 삭제된 행이 가장 마지막 행인 경우에는 바로 윗 행을 선택합니다.

마지막으로 네 번째, 'Z' 명령을 수행하면, 가장 최근에 삭제된 행을 원래대로 복구합니다.

단, 현재 선택된 행은 바뀌지 않습니다.

 

 

문제에 나와 있는 예시를 하나씩 볼까요?

 

왼쪽의 표에서 'D 2'를 수행할 경우 오른쪽의 그림처럼 4행이 선택됩니다.

 

 

그 다음에 'C'를 수행하면 선택된 행을 삭제하고,

바로 아래 행이었던 '네오'가 적힌 행을 선택합니다.

 

4행이 삭제되면서 아래 있던 행들이 하나씩 밀려 올라오고,

수정된 표에서 다시 4행을 선택하는 것과 동일하죠.

 

 

다음으로, 'U 3'을 수행한 다음,

'C'를 수행한 후의 표 상태는 오른쪽 그림과 같습니다.

 

 

다음으로 'D 4'를 수행한 다음 'C'를 수행한 후의 표 상태는 오른쪽 그림과 같습니다.

5행이 표의 마지막 행이므로, 이 경우에는 바로 윗 행을 선택하는 점에 주의해주세요!

 

 

다음으로 'U 2'를 수행하면 현재 선택된 행은 2행이 됩니다.

이 상태에서 'Z'를 수행할 경우 가장 최근에 제거된 '라이언'이 적힌 행이 원래대로 복구됩니다.

 

 

여기서 다시 한번 'Z'를 수행하면 그 다음으로 최근에 제거된 '콘'이 적힌 행이 원래대로 복구됩니다.

이때, 현재 선택된 행은 바뀌지 않는다는 점에 주의해주세요!

 

 

최종 표의 상태와 처음 주어진 표의 상태를 비교해서 삭제되지 않은 행은 'O',

삭제된 행은 'X'로 표시하면 다음과 같습니다.

삭제 스택에 남아있는 '프로도'를 아직 되돌리지 않았으니 'X'로 표시되는 것이죠.

 

 

문제 이해를 완료하셨을까요?

 

이제, 매개변수로 처음 표의 행 개수인 n,

처음에 선택된 행의 위치인 k,

수행한 명령어들이 담긴 문자열 배열인 cmd가 주어질 때,

 

모든 명령어를 수행한 후 표의 상태와

처음 주어진 표의 상태를 비교하여

삭제되지 않은 행은 'O',

삭제된 행은 'X'로 표시하여 문자열 형태로 반환해주는 함수를 완성해주면 됩니다.

 

제한사항

문제가 복잡할수록 제한사항도 꼼꼼히 잘 봐주셔야 합니다.

 

만약, 문제를 풀다가 시간초과가 날 경우

제한사항에 있는 범위를 고려하지 못한 코드일 확률이 높기 때문입니다.

 

그럼 제한사항을 하나씩 볼까요?

 

먼저, 행의 개수는 최대 100만, cmd의 개수는 최대 20만인 것을 볼 수 있습니다.

만약 행의 삭제를 배열 메서드인 `splice()`나 `shift()`를 이용한다면 어떻게 될까요?

삭제된 빈자리를 채우기 위해 뒤에 있는 요소들을 앞으로 한 칸씩 이동시켜야 합니다.

O(N)의 시간 복잡도를 가지게 되겠죠.

 

 

다음으로,

이전 문제 설명에서 봤듯이, '이름' 열은 딱히 필요하지 않습니다.

'몇 번째'의 행을 조작하는지가 중요했죠.

여기서 '이름'같은 데이터의 값보다,

순서를 중요하게 고려해야 한다는 것을 알 수 있습니다.

 

 

마지막으로,

행동이 불가능하거나, 조건을 고려해야 하는 명령들은 주어지지 않습니다.

이를 통해, 특수 케이스에 대한 처리는 신경을 크게 쓰지 않아도 되겠죠.

 

이렇게 모든 제한사항을 살펴보았습니다.

그런데 배열로 처리가 불가능할 것 같은데, 어떤 자료구조를 써야할까요?

중간 요소를 삭제하고, 삭제된 요소를 다시 원래 자리로 되돌리는데 좋은 자료구조가 있습니다.

바로 '연결 리스트' 입니다.

 

해결방법

연결리스트

'왜' 연결리스트를 사용해야 하는지 알아보기에 앞서,

연결리스트가 무엇인지 간단하게 먼저 살펴볼게요.

 

연결리스트는

'각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조'에요.

 

만약, 중간에 있는 데이터를 삭제하고 싶다면 어떻게 할까요?

예를 들어 2번 노드를 지운다고 생각해볼게요.

 

 

보시는 것과 같이,

기존에 1번에서 2번으로 연결되어 있던 포인터를

3번으로 연결해주기만 하면 됩니다.

 

그리고 2번 노드의 전과 후는 null로 해주면

연결이 끊어지므로 삭제된 것과 같은 효과를 줄 수 있죠.

 

 

문제는 표에 관한 문제니까,

노드는 각 행,

연결리스트는 표 전체라고 보면 됩니다.

 

자, 그럼 이제 코드를 구현해볼까요?

 

 

`Row`

먼저, 각 행을 나타내는 자료구조를 만들어줄게요.

`Row`라는 클래스로 나타내줄건데,

몇 번째인지 나타내는 `index`와

이전 행과 다음 행을 나타내는 포인터 변수인 `prev`와 `next`를 선언해줍니다.

 

 

`Table`

다음으로 표 전체를 나타내는 자료구조인 Table 클래스입니다.

 

각 행을 저장할 배열인 `rows`와

현재 위치를 나타내는 `cursor`,

삭제된 행들을 저장하는 `deletedStack` 변수를 선언해줍니다.

 

그런 다음에, 표를 초기화해줘야겠죠?

문제에서 매개변수로 행의 개수인 `n`과,

현재 위치를 나타내는 `k`를 받으니 그 변수를 이용해서 표를 초기화해주는 함수

`initTable()` 함수를 만들어보겠습니다.

 

 

Table - `initTable()`

`initTable()` 함수는 앞서 말씀드렸다시피,

행의 개수를 나타내는 `n`과,

현재 위치인 `k`를 매개변수로 받아요.

 

 

그리고 반복문을 통해 `n`개의 `Row`를 생성해주죠.

`Row`를 생성했지만, 서로 연결해주지 않았죠?

 

 

다시 한번 반복문을 통해

각 `Row`의 `prev`와 `next`를 연결해줄게요.

 

인덱스가 0보다 클 때는 현재 `Row`의 `prev`를 '이전 Row'와 연결해줍니다.

인덱스가 0인경우에는 `prev`가 없으니까 null인 상태에서 굳이 연결해줄 필요가 없겠죠.

 

마찬가지로, 인덱스가 n - 1보다 작을 때는 현재 `Row`의 `next`를 '다음 Row'랑 연결해줄게요.

여기도 마지막 행은 `next`가 없으니까 null로 그대로 두면 됩니다.

 

 

마지막으로, 현재 커서를 매개변수로 받은 `k`번째 `Row`로 할당해주면 됩니다.

 

 

만약 `n`이 3이고, `k`가 1이라면 왼쪽 그림과 같겠죠?

 

이렇게 기본적인 구조는 갖춰졌으니,

각 명령을 수행하는 함수도 만들어야 합니다.

 

X칸 위에 있는 행을 선택하는 `up()`함수,

X칸 아래에 있는 행을 선택하는 `down()`함수,

선택된 행을 삭제하는 `remove()` 함수,

행을 원래대로 복구하는 `restore()` 함수를 차례대로 만들어볼게요.

 

 

Table - `up()`

먼저, `up()` 함수입니다.

 

`moveCount`는 몇 칸 움직일지 받기 위한 매개변수입니다.

위로 움직여야 하기 때문에 `moveCount` 만큼 `prev`로 계속 거슬러 올라가면 되겠죠?

 

거슬러 올라가면서 `cursor`를 `prev`로 계속 갱신해줍니다.

 

만약, 초기에 왼쪽 그림처럼 `cursor`가 4행에 있고,

`moveCount`가 2라면,

 

 

4행의 `prev`인 3행으로 거슬러 올라가고,

 

 

3행의 `prev`인 2행으로 거슬러 올라가서 최종적으로 왼쪽의 그림과 같은 상황이 될거에요.

 

그럼 밑으로 가는 함수인 `down()`도 어떻게 구현해야 할지 감이 오시나요?

 

 

Table - `down()`

`down()`은 다음 행으로 가야하니, `prev`대신 `next`를 사용해서 해주면 됩니다.

 

 

Table - `remove()`

다음으로, 선택된 행을 삭제하는 함수인 `remove()` 함수를 살펴볼게요.

 

먼저, 삭제할 행을 `deletedRow`라는 변수에 저장해줄게요.

 

 

그 다음으로, 삭제 스택에 현재 행을 넣어줍니다.

이 때, 중요한것은 삭제할 행의 `prev`와 `next`도 같이 저장해줘야 한다는 것이에요.

Row 클래스의 `prev`와 `next` 속성으로 접근할 수 있는데 왜 따로 또 저장할까요?

 

 

행이 삭제된다면, 연결을 재조정 해주어야 합니다.

이 과정에서 연결이 끊어지게 되는데,

원래 연결되어 있던 `prev`와 `next`를 나중에 복구할 때 참조하기 위함입니다.

 

 

연결을 재조정 해주었다면,

마지막행이 아니라면 다음행으로,

마지막행이라면 이전행으로 커서를 옮겨줍니다.

 

 

Table - `restore()`

마지막으로 삭제된 행을 복구하는 `restore()` 함수입니다.

 

'가장 최근에 삭제된 행'을 복구하는 것이니,

`deletedStack`의 맨 위에 있는 것을 `pop()` 해주면 되겠죠?

 

 

그 다음으로, 우리가 스택에 넣을 때 같이 저장했던 prevRow와 nextRow를 이용해서

연결을 복구해주면 됩니다.

 

 

Table - `getResult()`

결과를 얻는 함수는 이렇게 간단하게 구현해주면 되겠죠?

아직 `deletedStack`에 남아있는 행은

삭제된 후, 복구되지 않은 행이기 때문에 해당 행만 'X'로 바꿔주시면 됩니다.

 

이렇게 구현에 필요한 모든 함수를 완성했습니다!

이제 입력에 맞게 결과를 구해볼까요?

 

 

`solution()`

Table 클래스의 인스턴스를 생성해준 뒤,

반복문으로 각 명령에 맞게 `switch`로 분기처리를 해주면 됩니다.

몇 칸 이동할지 나타내는 변수는 `parseInt()`로 정수로 변환한 뒤에 넘겨주는걸 잊지마세요!

 

이상 프로그래머스 Level3.

'표 편집' 문제 자바스크립트 풀이였습니다.

감사합니다!

 

 

전체 코드

class Row {
  constructor(index) {
    this.index = index;
    this.prev = null;
    this.next = null;
  }
}

class Table {
  constructor(n, k) {
    this.rows = [];
    this.cursor = null;
    this.deletedStack = [];
    this.initTable(n, k);
  }

  initTable(n, k) {
    for (let i = 0; i < n; i++) {
      this.rows[i] = new Row(i);
    }

    for (let i = 0; i < n; i++) {
      if (i > 0) this.rows[i].prev = this.rows[i - 1];
      if (i < n - 1) this.rows[i].next = this.rows[i + 1];
    }

    this.cursor = this.rows[k];
  }

  up(moveCount) {
    for (let i = 0; i < moveCount; i++) {
      this.cursor = this.cursor.prev;
    }
  }

  down(moveCount) {
    for (let i = 0; i < moveCount; i++) {
      this.cursor = this.cursor.next;
    }
  }

  remove() {
    const deletedRow = this.cursor;

    // 삭제할 때 prev/next 정보를 저장해두기
    this.deletedStack.push({
      row: deletedRow,
      prevRow: deletedRow.prev,
      nextRow: deletedRow.next,
    });

    // 연결 끊기
    if (deletedRow.prev) {
      deletedRow.prev.next = deletedRow.next;
    }
    if (deletedRow.next) {
      deletedRow.next.prev = deletedRow.prev;
    }

    // 커서 이동
    if (deletedRow.next) {
      this.cursor = deletedRow.next;
    } else {
      this.cursor = deletedRow.prev;
    }
  }

  restore() {
    if (this.deletedStack.length === 0) return;

    const { row: restoredRow, prevRow, nextRow } = this.deletedStack.pop();

    // 저장된 연결 정보로 즉시 복구 (O(1))
    restoredRow.prev = prevRow;
    restoredRow.next = nextRow;

    if (prevRow) {
      prevRow.next = restoredRow;
    }
    if (nextRow) {
      nextRow.prev = restoredRow;
    }
  }

  getResult() {
    const result = new Array(this.rows.length).fill('O');

    for (const { row } of this.deletedStack) {
      result[row.index] = 'X';
    }

    return result.join('');
  }
}

/**
 * 표 편집
 * @description 표에서 행을 선택, 삭제, 복구하는 명령어들을 수행한 후 최종 표의 상태를 구하는 함수
 * @param {number} n 표의 행 개수
 * @param {number} k 처음 선택된 행의 위치
 * @param {string[]} cmd 수행할 명령어 배열
 * @returns {string} 최종 표의 상태 ('O': 존재, 'X': 삭제)
 * @constraints
 * - 표의 행 개수 n은 5 이상 1,000,000 이하입니다.
 * - 처음 선택된 행의 위치 k는 0 이상 n-1 이하입니다.
 * - 명령어 배열 cmd의 길이는 1 이상 200,000 이하입니다.
 * - 명령어는 "U X", "D X", "C", "Z" 형태입니다.
 */
function solution(n, k, cmd) {
  const table = new Table(n, k);

  for (let i = 0; i < cmd.length; i++) {
    const [command, x] = cmd[i].split(' ');

    switch (command) {
      case 'U':
        table.up(parseInt(x));
        break;
      case 'D':
        table.down(parseInt(x));
        break;
      case 'C':
        table.remove();
        break;
      case 'Z':
        table.restore();
        break;
    }
  }

  const result = table.getResult();
  return result;
}