[프로그래머스] 표 병합(JavaScript)

🍀 목차
문제
설계
구현(JavaScript)
최종 코드

 

문제

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

프로그래머스

 

 

설계

 MERGE와 UNMERGE 명령어를 구현하는 데 많은 고민을 했다.

테스트에서는 위의 명령어를 Union-Find로 접근했었으나 구현과정에서 시간이 부족하여 해결하지 못했다.

다시 풀어보니 문제에서 주어진 표의 크기가 50X50으로 크지 않은 편이어서 완전 탐색과 구현으로 해결할 수 있었다.

 

문제 설명에서 주의 깊게 봐야 할 내용들은 다음과 같다.

 

• 각 셀은 문자열 값을 가짐 👉 문자열로만 이루어진 표이다(Number 같은 것으로 형변환 하지 않기).
• MERGE
  • 다른 셀과 병합될 수 있고 해제도 가능함 👉 (1) 어떤 셀에 포함되어 있는지 계속 확인해야 함.
  • 선택한 두 셀은 서로 인접하지 않을 수도 있음
  • 병합되었다면 어느 위치를 선택해도 병합된 셀로 접근함
• 부가적인 설계
  • 명령어 UPDATE, MERGE... 같은 문자열은 상수로 관리하면 편하다. 👉 오타가 발생해도 한 군데만 수정하면 된다.
  • 문제에서 주어진 R, C 값도 상수로 관리하면 좋다. 👉 프로그래머스 내에서 테스트 시 작은 R, C 출력 값을 확인하고 싶을 때 편하다.

 

 

 (1)에 대한 설계는 고민을 많이 했었는데 결국 RXCX2의 3차원 배열을 만들어 관리하기로 했다(뭔가 Map 자료구조를 떠올렸었다...). R행 C열의 각 셀 안에는 [해당 셀의 문자열 값, 어느 배열에 병합되어 있는가]의 배열이 들어가 있다.

 

 어느 배열에 병합되어 있는가는 문자열로 관리했다. 21행 3열의 셀에 1행 2열의 셀이 병합되게 된다면, 1행 2열의 셀의 1번째 인덱스에 '21,3' ('213' 같이 구분자가 없다면  2행 13열인지, 21행 3열인지 파악이 어려우니 구분자를 넣어야 한다.)를 넣는 식이다. 그림으로 설명하면 아래와 같다.

 

 

  1행 1열 셀과 3행 3열 셀을 선택하여 병합한다. 두 셀 모두 값을 가지고 있기에 1행 1열 셀 값으로 업데이트된 후, 3행 3열은 1행 1열 셀과 병합되었다고 표시한다.

 

 

  1행 1열 셀과 3행 3열 셀을 선택하여 병합한다. 두 셀 모두 값을 가지고 있기에 1행 1열 셀 값으로 업데이트된 후, 3행 3열은 1행 1열 셀과 병합되었다고 표시한다. 주의할 것이 있다면 기존 3행 3열과 병합되었던 셀 모두 1행 1열로 값과 병합 정보가 업데이트되어야 한다.

 

구현(JavaScript)

 명령어, R,C를 상수로 선언했다.

const STR_EMPTY = "EMPTY";
const STR_UPDATE = "UPDATE";
const STR_MERGE = "MERGE";
const STR_UNMERGE = "UNMERGE";
const STR_PRINT = "PRINT";
const R = 51;
const C = 51;

 

 RXCX2의 3차원 배열을 선언한다.

 const table = Array.from({length:R},()=> Array.from({length:C},()=>["",undefined]));

 

Array.from()을 활용하여 배열에 배열을 중첩시켜 만들었다.

 

어느 배열에 포함되어 있는지는 getKey라는 함수를 만들어 초깃값과 재사용을 하였다.

 const getKey = (r,c)=>{
        return `${r},${c}`;
    }
    
    
    //초기화
     for(let r=1;r<R;r++){
        for(let c=1;c<C;c++){
            table[r][c][1] = getKey(r,c);
        }
    }

 

 

 그 외의 코드들은 주어진 제한사항을 유의하며 구현하면 된다.

최종 코드

 

function solution(commands) {
  const STR_EMPTY = 'EMPTY';
  const STR_UPDATE = 'UPDATE';
  const STR_MERGE = 'MERGE';
  const STR_UNMERGE = 'UNMERGE';
  const STR_PRINT = 'PRINT';
  const R = 51;
  const C = 51;
  const table = Array.from({ length: R }, () =>
    Array.from({ length: C }, () => ['', undefined]),
  );
  const answer = [];

  const getKey = (r, c) => {
    return `${r},${c}`;
  };

  for (let r = 1; r < R; r++) {
    for (let c = 1; c < C; c++) {
      table[r][c][1] = getKey(r, c);
    }
  }

  const merging = (r1, c1, r2, c2) => {
    if (Math.abs(r1 - r2) + Math.abs(c1 - c2) === 0) {
      return;
    }

    let value = '';
    const R1C1Key = table[r1][c1][1];
    const R2C2Key = table[r2][c2][1];

    if (table[r2][c2][0] !== '') {
      value = table[r2][c2][0];
    }

    if (table[r1][c1][0] !== '') {
      value = table[r1][c1][0];
    }

    for (let r = 1; r < R; r++) {
      for (let c = 1; c < C; c++) {
        if (table[r][c][1] === R1C1Key) {
          table[r][c][0] = value;
        }
        if (table[r][c][1] === R2C2Key) {
          table[r][c][0] = value;
          table[r][c][1] = R1C1Key;
        }
      }
    }
  };

  commands.forEach(command => {
    const [keyword, ...orders] = command.split(' ');

    switch (keyword) {
      case STR_UPDATE:
        if (orders.length === 3) {
          const [r, c, value] = orders;
          const mergeKey = table[r][c][1];

          for (let r = 1; r < R; r++) {
            for (let c = 1; c < C; c++) {
              if (table[r][c][1] === mergeKey) {
                table[r][c][0] = value;
              }
            }
          }

          table[+r][+c][0] = value;
        } else {
          const [value1, value2] = orders;
          for (let r = 1; r < R; r++) {
            for (let c = 1; c < C; c++) {
              if (table[r][c][0] === value1) {
                table[r][c][0] = value2;
              }
            }
          }
        }
        break;
      case STR_MERGE:
        const [r1, c1, r2, c2] = orders.map(order => Number(order));
        merging(r1, c1, r2, c2);
        break;
      case STR_UNMERGE:
        const [r, c] = orders.map(order => Number(order));
        const mergeKey = table[r][c][1];
        const mergeValue = table[r][c][0];

        for (let r = 1; r < R; r++) {
          for (let c = 1; c < C; c++) {
            if (table[r][c][1] === mergeKey) {
              table[r][c][0] = '';
              table[r][c][1] = getKey(r, c);
            }
          }
        }
        table[r][c][0] = mergeValue;
        break;
      case STR_PRINT:
        const [printR, printC] = orders.map(order => Number(order));
        if (table[printR][printC][0] === '') {
          answer.push(STR_EMPTY);
        } else {
          answer.push(table[printR][printC][0]);
        }
        break;
      default:
        break;
    }
  });

  return answer;
}