프로그래머스 표 병합 - 자바스크립트 | 기록할 때 나는 더 분명해진다

📄 문제

프로그래머스 > 2023 KAKAO BLIND RECRUITMENT > 표 병합

구현해야 하는 것은

표를 두고 명령어에 따라 셀의 값을 변경해야 한다.

명령의 종류는 총 5가지로 다음과 같다.

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

1️⃣ 셀의 값을 저장할 배열과 참조하는 셀의 위치를 저장할 배열을 선언한다.

가장 주목해야 할 명령어는 MERGE와 UNMERGE다. MERGE된 셀은 본인 값 대신 병합된 셀의 값을 갖는다.(앞으로 병합된 셀을 상위 병합이라고 하겠다.) 때문에 상위 병합을 기억하고 있어야 한다.

(1)셀의 값을 저장할 배열과 (2)상위 병합을 저장할 배열을 각각 선언하고 초기화한다. 표의 크기는 50 x 50으로 고정되어 있고, 1번 인덱스부터 사용하기 위해 51 x 51인 2차원 배열을 사용한다.

  
function solution(commands) {
  // 초기의 모든 셀은 비어 있다.
  // 그리고 PRINT 명령에서 빈 값은 "EMPTY"로 출력하기 때문에 "EMPTY"로 초기화한다.
  const arr = Array.from({ length: 51 }, () =>
    Array.from({ length: 51 }, () => "EMPTY")
  );
  // 초기에는 본인 셀의 값을 가리킨다. 그러므로 최초 값은 본인 위치를 저장한다. "i, j" 포맷으로 저장한다.
  const parent = Array.from({ length: 51 }, (_, i) =>
    Array.from({ length: 51 }, (_, j) => `${i},${j}`)
  );
}

두 배열을 초기화하면 다음과 같다.

init-arr-and-parent

2️⃣ 가장 복잡한 MERGE 명령에 대한 기능부터 구현하자.

MERGE를 구현하기 위해서 주의해야 할 점은 두 가지다. 하나는 두 셀 중 한 셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지게 되는 것이고, 또 하나는 이미 다른 셀에 병합된 셀을 처리하는 것이다.

MERGE r1 c1 r2 c2에서 기본적으로 (r2, c2)가 (r1, c1)으로 병합되는데 (r1, c1)이 빈 값이라면 반대로 병합을 수행하라는거다.

초기 상태에서 MERGE 1 1 2 1라는 명령어가 실행해보자. 이 때, 두 셀 모두 값이 있다고 가정한다.

(2, 1)가 (1, 1)으로 병합된다. 즉, (2, 1)의 상위 병합은 (1, 1)이다. 따라서 parent[2][1]은 “1,1”이라는 값을 얻게 된다. 그리고 (2, 1)에 접근했을 때 (1, 1) 값을 반환해야 한다. 이 때, 값을 찾을 때마다 (1, 1)을 찾아가서 값을 얻어와도 되지만 병합 관계가 커진다면 시간이 오래 걸릴 것이다.

바로 값을 반환하기 위해 상위 병합 값을 본인 셀에 저장한다. 그럼 arr[1][1]은 arr[2][1]의 값이 된다.

merge-1

하나의 MERGE 명령이 실행되고, 병합당하는 셀이 (r, c)라면 parent[r][c]와 arr[r][c]이 갱신된다.

여기서 MERGE 1 1 1 2를 실행하면 위와 동일하게 arr[1][2]와 parent[1][2]가 갱신된다.

merge-2

이번엔 초기 상태에서 MERGE 2 3 3 3라는 명령어가 실행해보자. 이번엔 두 번째 셀만 값이 있다고 가정한다.

(2, 3)은 비어있기 때문에 (2, 3)이 (3, 3)으로 병합된다. 따라서 parent[2][3]은 “3,3”이라는 값을 얻고 arr[2][3]은 arr[3][3]이 가진 값으로 갱신된다.

merge-3

여기서 MERGE 2 2 2 3 명령을 실행해보자. (2, 2)는 비어있기 때문에 (2, 3)으로 병합된다. (2, 3)은 이미 (3, 3)에 병합되어 있다. 그러므로 (2, 2) -> (2, 3) -> (3, 3)으로 병합된다. 따라서 (2, 2)의 상위 병합은 (3, 3)이 된다.

arr[2][2]은 어떤 값을 가져야 할까? 병합 시 본인 셀을 상위 병합의 값으로 갱신하기로 했으므로 arr[3][3]까지 찾아가서 값을 가져오지 않고 arr[2][3]의 값으로 갱신하면 된다. 참조 값 역시 parent[2][3]이 가진 값으로 갱신해주면 된다.

merge-4

한 번만 더 해보자. 위와 같은 병합관계일 때, MERGE 3 1 2 2 명령을 수행해보겠다. 이 때, (3, 1)은 값이 있다고 가정한다.

명령대로라면 (2, 2)가 (3, 1)로 병합된다. 현재 (2, 2)는 (3, 3)에 병합되어 있다. 그러므로 (3, 3)이 (3, 1)로 병합되고, (3, 3)에 병합된 셀들도 (3, 1)로 병합되는 것이다. 즉, (2, 2) -> (2, 3) -> (3, 3) -> (3, 1)으로 병합되었고, 결론적으로 (2, 2), (2, 3), (3, 3)의 상위 병합은 (3, 1)인 것이다.

따라서 병합되는 셀이 다른 셀에 이미 병합되어 있다면 병합되는 셀의 상위 병합과 이 상위 병합에 병합된 모든 셀들의 값과 참조 셀의 위치를 변경해줘야 한다. 아래 그림을 보면 이해가 쉬울 것이다.

merge-5

이제 다시 처음으로 돌아가보자. MERGE r1 c1 r2 c2에서 (r1, c1)이 비어있으면 (r2, c2)으로 병합되고, 그게 아니면 (r2, c2)가 (r1, c1)으로 병합된다.

무조건 (r2, c2)가 (r1, c1)에 병합되도록 한다면 조건문을 제거할 수 있고 이해하기 수월하다.

그러기 위해서 MERGE가 수행되면 처음으로 (r1, c1)과 (r2, c2)이 각각 비어있는지 체크해보자. (r1, c1)이 빈 값이고 (r2, c2)가 빈 값이 아니라면 구조분해 할당을 통해 서로 값을 교환하면 원하던대로 무조건 (r2, c2)이 (r1, c1)으로 병합된다.

코드로 확인해보자.

  
function merge(r1, c1, r2, c2) {
  // (r1, c1)이 비었다면 (r2, c2)로 병합되어야 하므로
  // r2를 r1으로, c2를 c1으로 변경하고 반대로도 적용한다.(구조 분해 할당 사용)
  if (arr[r1][c1] === "EMPTY" && arr[r2][c2] !== "EMPTY")
    [r1, c1, r2, c2] = [r2, c2, r1, c1];

  // 갱신되는 값은 (r1, c1)이 가진 값이다.
  let new_value = arr[r1][c1];

  // 단순히 (r2, c2)의 참조 값만 변경하는 것이 아니다.
  // (r2, c2)가 참조하던 값(병합당한 셀의 위치)과 그 셀을 참조하는 모든 셀들의 참조 값을 (r1, c1)으로 갱신해야 한다.
  let change_pointer = parent[r2][c2];

  for (let i = 1; i <= 50; i++) {
    for (let j = 1; j <= 50; j++) {
      if (parent[i][j] === change_pointer) {
        parent[i][j] = parent[r1][c1];
        arr[i][j] = new_value;
      }
    }
  }
}

3️⃣ UNMERGE 명령에 대한 기능을 구현하자.

UNMERGE r c명령이 수행되면 (r, c)에 연결된 병합 관계를 모두 해제한다. 이건 (r, c)의 상위 병합과 그 상위 병합에 병합된 모든 셀을 초기 상태로 바꿔야 한다는 의미다. 초기 상태란 arr는 “EMPTY”로, parent는 본인 위치를 갖는 것이다. 그리고 (r, c)가 원래 값을 가지고 있었다면 그 값은 유지해야 한다.

위 MERGE를 설명하며 만든 병합 관계에서 UNMERGE 2 3 명령을 수행해보자.

(2, 3)에 연결된 병합관계는 (2, 2) -> (2, 3) -> (3, 3) -> (3, 1)이다. 즉, (2, 3)의 상위 병합인 (3, 1)과 (3, 1)에 병합된 모든 셀을 초기화시키면 된다.

그리고 병합 해제 전 (2, 3)은 (3, 1)의 값을 갖고 있었다. arr[2][3]에는 병합 명령을 수행하며 arr[3][1]의 값이 들어있다. 그러므로 arr[2][3]의 본인 값 그대로 유지해야 한다.

unmerge-1

  
function unmerge(r, c) {
  // (r, c)의 값은 유지하기 위해 임시 변수에 넣어둔다.
  let value = arr[r][c];

  // (r, c)가 참조하는 셀의 위치를 담아둔다.
  let change_pointer = parent[r][c];

  for (let i = 1; i <= 50; i++) {
    for (let j = 1; j <= 50; j++) {
      // (r, c)가 참조하는 parent를 참조하는 모든 셀의 값을 초기화한다.
      if (parent[i][j] === change_pointer) {
        // 참조의 경우 본인 위치로 갱신하고,
        parent[i][j] = `${i},${j}`;

        // 값의 경우 빈 값을 의미하는 "EMPTY"로 갱신한다.
        arr[i][j] = "EMPTY";
      }
    }
  }

  // 병합 해제 전 값을 가진 경우 그 값을 그대로 유지해야 하므로 갱신한다.
  arr[r][c] = value;
}

4️⃣ 첫 번째 UPDATE 명령에 대한 기능을 구현하자.

UPDATE r c value 명령은 (r, c)를 value로 갱신시킨다. 이 때, (r, c)가 다른 셀에 병합된 상태라면 (r, c)가 아닌 상위 병합의 값을 갱신해야 한다. 그리고 상위 병합에 병합된 모든 셀들의 값도 변경해야 한다. (병합 명령 시 상위 병합 값을 본인 셀에 저장해뒀기 때문에 상위 병합 값이 변한다면 본인도 변경해줘야 하기 때문이다.)

update1-1

위 그림에서 (2, 2), (2, 3), (3, 3)은 모두 (3, 1)에 병합된 상태다. 이 때, UPDATE 2 2 🍎 명령은 (2, 2)뿐만 아니라 (2, 2)의 상위 병합인 (3, 1)과 (3, 1)에 병합된 (2, 3)과 (3, 3)까지 모두 🍎으로 갱신해야 한다.

UPDATE 명령을 수행해도 병합 관계가 변하는 것은 아니다. 값만 변경되는 것이다.

  
function update_1(r, c, value) {
  for (let i = 1; i <= 50; i++) {
    for (let j = 1; j <= 50; j++) {
      // (r, c)가 참조하는 셀을 참조하는 모든 셀의 값은 수정되어야 한다.
      if (parent[i][j] === parent[r][c]) arr[i][j] = value;
    }
  }
}

5️⃣ 두 번째 UPDATE 명령에 대한 기능을 구현하자.

UPDATE value1 value2는 value1을 가진 셀을 value2로 갱신해주기만 하면 된다. 이 때도 병합 관계는 고려하지 않아도 된다.

  
function update_2(value1, value2) {
  for (let i = 1; i <= 50; i++) {
    for (let j = 1; j <= 50; j++) {
      if (arr[i][j] === value1) arr[i][j] = value2;
    }
  }
}

6️⃣ 마지막으로 PRINT 명령에 대한 기능을 구현하자.

문제의 최종 답은 PRINT 명령 시 해당 셀의 값을 반환하는 것이다. 따라서 PRINT r c 명령이 수행되면 arr[r][c]을 반환하면 된다.

병합 관계를 고려하지 않고 (r, c)가 가지고 있는 값을 반환할 수 있는 이유는 병합 명령을 수행할 때, 상위 병합 값을 본인 셀에 담고 있기 때문이다.

  
const answer = [];
function print(r, c) {
  answer.push(arr[r][c]);
}

7️⃣ 명령어를 switch문으로 하나씩 수행하고 실행 결과를 임시 배열에 담아 return하면 된다.

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

  commands.forEach((command) => {
    const [cmd, option1, option2, option3, option4] = command.split(" ");
    switch (cmd) {
      case "UPDATE":
        if (option3) {
          update_1(option1, option2, option3);
        } else {
          update_2(option1, option2);
        }
        break;
      case "MERGE":
        merge(option1, option2, option3, option4);
        break;
      case "UNMERGE":
        unmerge(option1, option2);
        break;
      case "PRINT":
        print(option1, option2);
        break;
    }
  });

  return answer;
}

🏹 코드

  
function solution(commands) {
  const answer = [];
  const parent = Array.from({ length: 51 }, (_, i) =>
    Array.from({ length: 51 }, (_, j) => `${i},${j}`)
  );
  const arr = Array.from({ length: 51 }, () =>
    Array.from({ length: 51 }, () => "EMPTY")
  );

  function update_1(r, c, value) {
    for (let i = 1; i <= 50; i++) {
      for (let j = 1; j <= 50; j++) {
        if (parent[i][j] === parent[r][c]) arr[i][j] = value;
      }
    }
  }

  function update_2(value1, value2) {
    for (let i = 1; i <= 50; i++) {
      for (let j = 1; j <= 50; j++) {
        if (arr[i][j] === value1) arr[i][j] = value2;
      }
    }
  }

  function merge(r1, c1, r2, c2) {
    if (arr[r1][c1] === "EMPTY" && arr[r2][c2] !== "EMPTY")
      [r1, c1, r2, c2] = [r2, c2, r1, c1];

    let new_value = arr[r1][c1];
    let change_pointer = parent[r2][c2];

    for (let i = 1; i <= 50; i++) {
      for (let j = 1; j <= 50; j++) {
        if (parent[i][j] === change_pointer) {
          parent[i][j] = parent[r1][c1];
          arr[i][j] = new_value;
        }
      }
    }
  }

  function unmerge(r, c) {
    let value = arr[r][c];
    let change_pointer = parent[r][c];

    for (let i = 1; i <= 50; i++) {
      for (let j = 1; j <= 50; j++) {
        if (parent[i][j] === change_pointer) {
          parent[i][j] = `${i},${j}`;
          arr[i][j] = "EMPTY";
        }
      }
    }
    arr[r][c] = value;
  }

  function print(r, c) {
    answer.push(arr[r][c]);
  }

  commands.forEach((command) => {
    const [cmd, option1, option2, option3, option4] = command.split(" ");
    switch (cmd) {
      case "UPDATE":
        if (option3) {
          update_1(option1, option2, option3);
        } else {
          update_2(option1, option2);
        }
        break;
      case "MERGE":
        merge(option1, option2, option3, option4);
        break;
      case "UNMERGE":
        unmerge(option1, option2);
        break;
      case "PRINT":
        print(option1, option2);
        break;
    }
  });

  return answer;
}

👩‍🌾 새로 알게 되었거나 중요한 포인트

구글링하면서 이 문제를 union-find로 해결할 수 있다는 블로그 글을 읽었다. union-find가 뭔지 몰랐는데 이 방식이 유사한게 아닌가 생각된다.

상위 병합의 값을 가져와야 할 때, 상위 병합의 값을 찾으러 가서 반환하지 않고 병합 당시에 그 값을 본인이 가지고 있으므로써 시간을 절약할 수 있다.

union-find는 조금 더 알아봐야겠다. 필요하다면 아래 블로그들을 참고하자.

🐝 참고
서로소 집합(Disjoint Set) & 유니온 파인드(Union find)
[알고리즘] Union-Find 알고리즘 - Heee’s Development Blog
velog(woohoo.log) - [알고리즘] union-find 알고리즘

프로그래머스 표 병합 - 자바스크립트