[Algorithm] 표 병합

📋 문제 

당신은 표 편집 프로그램을 작성하고 있습니다.
표의 크기는 50 × 50으로 고정되어있고 초기에 모든 셀은 비어 있습니다.
각 셀은 문자열 값을 가질 수 있고, 다른 셀과 병합될 수 있습니다.

위에서 r번째, 왼쪽에서 c번째 위치를 (r, c)라고 표현할 때, 당신은 다음 명령어들에 대한 기능을 구현하려고 합니다.

1. "UPDATE r c value"
   
   • (r, c) 위치의 셀을 선택합니다.
   • 선택한 셀의 값을 value로 바꿉니다.
2. "UPDATE value1 value2"
   
   • value1을 값으로 가지고 있는 모든 셀을 선택합니다.
   • 선택한 셀의 값을 value2로 바꿉니다.
3. "MERGE r1 c1 r2 c2"
   
   • (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀을 선택하여 병합합니다.
   • 선택한 두 위치의 셀이 같은 셀일 경우 무시합니다.
   • 선택한 두 셀은 서로 인접하지 않을 수도 있습니다. 이 경우 (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀만 영향을 받으며, 그 사이에 위치한 셀들은 영향을 받지 않습니다.
   • 두 셀 중 한 셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지게 됩니다.
   • 두 셀 모두 값을 가지고 있을 경우 병합된 셀은 (r1, c1) 위치의 셀 값을 가지게 됩니다.
   • 이후 (r1, c1) 와 (r2, c2) 중 어느 위치를 선택하여도 병합된 셀로 접근합니다.
4. "UNMERGE r c"
   
   • (r, c) 위치의 셀을 선택하여 해당 셀의 모든 병합을 해제합니다.
   • 선택한 셀이 포함하고 있던 모든 셀은 프로그램 실행 초기의 상태로 돌아갑니다.
   • 병합을 해제하기 전 셀이 값을 가지고 있었을 경우 (r, c) 위치의 셀이 그 값을 가지게 됩니다.
5. "PRINT r c"
   
   • (r, c) 위치의 셀을 선택하여 셀의 값을 출력합니다.
   • 선택한 셀이 비어있을 경우 "EMPTY"를 출력합니다.

아래는 UPDATE 명령어를 실행하여 빈 셀에 값을 입력하는 예시입니다.

commands	효과
UPDATE 1 1 menu	(1,1)에 "menu" 입력
UPDATE 1 2 category	(1,2)에 "category" 입력
UPDATE 2 1 bibimbap	(2,1)에 "bibimbap" 입력
UPDATE 2 2 korean	(2,2)에 "korean" 입력
UPDATE 2 3 rice	(2,3)에 "rice" 입력
UPDATE 3 1 ramyeon	(3,1)에 "ramyeon" 입력
UPDATE 3 2 korean	(3,2)에 "korean" 입력
UPDATE 3 3 noodle	(3,3)에 "noodle" 입력
UPDATE 3 4 instant	(3,4)에 "instant" 입력
UPDATE 4 1 pasta	(4,1)에 "pasta" 입력
UPDATE 4 2 italian	(4,2)에 "italian" 입력
UPDATE 4 3 noodle	(4,3)에 "noodle" 입력

위 명령어를 실행하면 아래 그림과 같은 상태가 됩니다.

 

아래는 MERGE 명령어를 실행하여 셀을 병합하는 예시입니다.

commands	효과
MERGE 1 2 1 3	(1,2)와 (1,3) 병합
MERGE 1 3 1 4	(1,3)과 (1,4) 병합

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

병합한 셀은 "category" 값을 가지게 되며 (1,2), (1,3), (1,4) 중 어느 위치를 선택하더라도 접근할 수 있습니다.

아래는 UPDATE 명령어를 실행하여 셀의 값을 변경하는 예시입니다.

commands	효과
UPDATE korean hansik	"korean"을 "hansik"으로 변경
UPDATE 1 3 group	(1,3) 위치의 셀 값을 "group"으로 변경

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

 

아래는 UNMERGE 명령어를 실행하여 셀의 병합을 해제하는 예시입니다.

 

commands	효과
UNMERGE 1 4	셀 병합 해제 후 원래 값은 (1,4)가 가짐

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

실행할 명령어들이 담긴 1차원 문자열 배열 commands가 매개변수로 주어집니다. commands의 명령어들을 순서대로 실행하였을 때, "PRINT r c" 명령어에 대한 실행결과를 순서대로 1차원 문자열 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ commands의 길이 ≤ 1,000
• commands의 각 원소는 아래 5가지 형태 중 하나입니다.
  
  1. "UPDATE r c value"
     
     • r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
     • value는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
  2. "UPDATE value1 value2"
     
     • value1은 선택할 셀의 값, value2는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
  3. "MERGE r1 c1 r2 c2"
     
     • r1, c1, r2, c2는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
  4. "UNMERGE r c"
     
     • r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
  5. "PRINT r c"
     
     • r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
• commands는 1개 이상의 "PRINT r c" 명령어를 포함하고 있습니다.

입출력 예

["UPDATE 1 1 menu", "UPDATE 1 2 category", "UPDATE 2 1 bibimbap", "UPDATE 2 2 korean", "UPDATE 2 3 rice", "UPDATE 3 1 ramyeon", "UPDATE 3 2 korean", "UPDATE 3 3 noodle", "UPDATE 3 4 instant", "UPDATE 4 1 pasta", "UPDATE 4 2 italian", "UPDATE 4 3 noodle", "MERGE 1 2 1 3", "MERGE 1 3 1 4", "UPDATE korean hansik", "UPDATE 1 3 group", "UNMERGE 1 4", "PRINT 1 3", "PRINT 1 4"]	["EMPTY", "group"]
["UPDATE 1 1 a", "UPDATE 1 2 b", "UPDATE 2 1 c", "UPDATE 2 2 d", "MERGE 1 1 1 2", "MERGE 2 2 2 1", "MERGE 2 1 1 1", "PRINT 1 1", "UNMERGE 2 2", "PRINT 1 1"]	["d", "EMPTY"]

✏️ 풀이

셀이 50 x 50으로 고정되어 있기 때문에 이차원 배열(cell)을 각각 51길이로 선언했다. PRINT 명령어를 실행할 때 문자열의 falsy값을 사용하기 위해 초기값은 빈 문자열을 넣어줬다. 명령어에 따라 함수를 만들어줬다. 

 

병합(MERGE)을 고려하는 것이 제일 고민이었는데 병합됬는지를 확인하는 mergeCheck라는 이차원 배열을 선언하고 초기값으로는 현재 자신의 인덱스를 가지도록 했다. 이 값이 만약 자기 자신의 인덱스와 일치하는 값을 가진 경우에는 병합이 되지 않거나, 병합된 것 중 기준이 되는 셀을 가르키는 경우이고, 만약 다르다면 특정 셀과 병합된 것이다. 셀들이 하나로 병합될 때 병합되는 모든 셀은 기준이 되는 셀을 가르키게 되는데 이는 값을 가지고 있는 셀이 된다. 내가 코드를 작성할 때는 MERGE 명령어를 실행할 때 앞에 오는 위치의 셀을 기준으로 했다. 예시를 보면 이해하기 쉽다.

 

2x2를 기준으로 한다면 mergeCheck 배열의 초기값은 다음과 같다.

[1, 1]	[1, 2]
[2, 1]	[2, 2]

 

만약 [1, 1]과 [1, 2]를 병합한다면 다음과 같이 표기된다. 앞에 있는 값 [1, 1]의 셀이 기준이 된다.

[1, 1]	[1, 1]
[2, 1]	[2, 2]

 

병합되어 있는 셀과 합칠때에도 마찬가지이다. [1, 1]과 [2, 1]을 병합하면 다음과 같이 된다.

[1, 1]	[1, 1]
[1, 1]	[2, 2]

 

이때 병합된 값들은 모두 ''를 가지도록 하고(cell) 기준이 되는 셀만 입력된 값을 가진다.

 

UNMERGE 명령어의 경우 checkMerge값에서 기준이 되는 셀을 찾는다. 기준이 되는 셀에 값을 임시로 저장하고 checkMerge를 순회하며 값이 같을 때(기준이 되는 셀과 병합이 되어있을 때) 자기 자신의 위치를 의미하는 인덱스로 갱신시켜주고 모든 값을 ''로 초기화 해준 다음에 UNMERGE를 수행하는 셀에 저장해두었던 값을 할당한다.

 

UPDATE 명령어인 경우에는 두가지로 나뉠 수 있다. 각 명령어를 split으로 분리했을 때 길이에 따라 함수를 실행하면 된다. 특정 셀의 위치값이 들어온경우(r, c, vale가 존재할 때) cell에서 해당 위치의 값을 갱신한다. 이때 병합되어 있는지를 고려하여 mergeCheck에서 기준이 되는 셀을 r, c로 가져와서 변경한다. 만약 특정 값을 다른 값으로 변경하는 경우에는(value1, value2가 존재할 때) 표의 크기가 크지 않기 때문에 전체를 돌면서 특정값을 변경할 값으로 바꿔준다.

 

PRINT 명령어인 경우에는 병합되어 있는지를 고려하여 mergeCheck 배열에서 r, c값으로 기준이 되는 셀의 새로운 인덱스(checkR, checkC)값을 가져온다. 이때 이 값이 빈 문자열('')일 때는 'EMPTY'를 반환하고 아니라면 있는 값을 반환한다.

 

⌨️ 코드

function solution(commands) {
  var answer = [];

  const cell = [...Array(51)].map(_ => new Array(51).fill(''));
  const mergeCheck = [...Array(51)].map(_ => new Array(51));
  for (let i = 1; i < 51; i++) {
    for (let j = 1; j < 51; j++) {
      mergeCheck[i][j] = [i, j];
    }
  }

  const updateOne = (r, c, value) => {
    const [checkR, checkC] = mergeCheck[r][c];
    cell[checkR][checkC] = value;
  };

  const update = (value1, value2) => {
    for (let i = 1; i < 51; i++) {
      for (let j = 1; j < 51; j++) {
        if (cell[i][j] === value1) cell[i][j] = value2;
      }
    }
  };

  const merge = (r1, c1, r2, c2) => {
    const [checkR1, checkC1] = mergeCheck[r1][c1];
    const [checkR2, checkC2] = mergeCheck[r2][c2];
    const value = cell[checkR1][checkC1] || cell[checkR2][checkC2];

    for (let i = 1; i < 51; i++) {
      for (let j = 1; j < 51; j++) {
        const [checkI, checkJ] = mergeCheck[i][j];
        if (checkI === checkR1 && checkJ === checkC1) mergeCheck[i][j] = [checkR1, checkC1];
        else if (checkI === checkR2 && checkJ === checkC2) mergeCheck[i][j] = [checkR1, checkC1];
        else continue;
        cell[i][j] = '';
      }
    }
    updateOne(checkR1, checkC1, value);
  };

  const unmerge = (r, c) => {
    const [checkR, checkC] = mergeCheck[r][c];
    const value = cell[checkR][checkC];
    for (let i = 1; i < 51; i++) {
      for (let j = 1; j < 51; j++) {
        const [checkI, checkJ] = mergeCheck[i][j];
        if (checkI === checkR && checkJ === checkC) {
          mergeCheck[i][j] = [i, j];
          cell[i][j] = '';
        }
      }
    }
    updateOne(r, c, value);
  };

  const print = (r, c) => {
    const [checkR, checkC] = mergeCheck[r][c];
    answer.push(cell[checkR][checkC] ? cell[checkR][checkC] : 'EMPTY');
  };

  for (const command of commands) {
    const cmd = command.split(' ');
    if (cmd[0] === 'UPDATE') {
      if (cmd.length === 4) updateOne(cmd[1], cmd[2], cmd[3]);
      else update(cmd[1], cmd[2]);
    } else if (cmd[0] === 'MERGE') {
      merge(cmd[1], cmd[2], cmd[3], cmd[4]);
    } else if (cmd[0] === 'UNMERGE') {
      unmerge(cmd[1], cmd[2]);
    } else if (cmd[0] === 'PRINT') {
      print(cmd[1], cmd[2]);
    }
  }

  return answer;
}