문제 설명
당신은 표 편집 프로그램을 작성하고 있습니다.
표의 크기는 50 × 50으로 고정되어있고 초기에 모든 셀은 비어 있습니다.
각 셀은 문자열 값을 가질 수 있고, 다른 셀과 병합될 수 있습니다.
위에서 r번째, 왼쪽에서 c번째 위치를 (r, c)라고 표현할 때, 당신은 다음 명령어들에 대한 기능을 구현하려고 합니다.
- "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"를 출력합니다.
아래는 UPDATE 명령어를 실행하여 빈 셀에 값을 입력하는 예시입니다.
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 명령어를 실행하여 셀을 병합하는 예시입니다.
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 명령어를 실행하여 셀의 값을 변경하는 예시입니다.
UPDATE korean hansik "korean"을 "hansik"으로 변경
UPDATE 1 3 group (1,3) 위치의 셀 값을 "group"으로 변경
위 명령어를 실행하면 아래와 같은 상태가 됩니다.
아래는 UNMERGE 명령어를 실행하여 셀의 병합을 해제하는 예시입니다.
UNMERGE 1 4 셀 병합 해제 후 원래 값은 (1,4)가 가짐
위 명령어를 실행하면 아래와 같은 상태가 됩니다.
실행할 명령어들이 담긴 1차원 문자열 배열 commands가 매개변수로 주어집니다. commands의 명령어들을 순서대로 실행하였을 때, "PRINT r c" 명령어에 대한 실행결과를 순서대로 1차원 문자열 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
1 ≤ commands의 길이 ≤ 1,000
commands의 각 원소는 아래 5가지 형태 중 하나입니다.
"UPDATE r c value"
r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
value는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
"UPDATE value1 value2"
value1은 선택할 셀의 값, value2는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
"MERGE r1 c1 r2 c2"
r1, c1, r2, c2는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
"UNMERGE r c"
r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
"PRINT r c"
r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
commands는 1개 이상의 "PRINT r c" 명령어를 포함하고 있습니다.
입출력 예
입력1
"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"
출력1
(1,3) 위치의 셀은 비어있고 (1,4) 위치의 셀 값은 "group"입니다. 따라서 ["EMPTY", "group"]을 return 해야 합니다.
풀이
문제를 처음 읽고 든 생각은 각 명령어 마다 함수를 생성해주고 각각 요구사항에 맞게 풀면 되겠다 생각했는지만 호락호락하지 않았다(역시 카카오 ㄷㄷ😭)
핵심구현이라고 생각한것은 MERGE 명령어였다.
예들 들어 위 그림과 같이 두 집합 A,B가 있다고 가정해보자(초기화된 상태보다는 병합된 상태가 핵심이기에 미리 병합된 집합을 예시로 들었어요)
MERGE 1 1 2 2
위 command가 있다고 하면 1,1은 A집합 2,2는 B집합에 속해있는 상태다. 여기서 MERGE를 하면 또 다른 집합 C가 생성되고 이 집합의 인자는 (1,1),(1,2),(2,2),(2,3) 총 4개를 가진다. 이 과정에 탐색과 집합 A,B 인자의 모든 위치에 새로운 배열 C를 넣어줘야하기에 메모리 초과가 발생하여 에러를 일으킨다. 그림으로 표현하면 아래와 같다.
이를 해결하기 위해 union 알고리즘을 사용하였다. union알고리즘은 두 집합을 합칠 때 공통인자를 가진 값을 넣어 두 집합이 하나라는 표시를 해주는 것이다. 그림을 살펴보자
위 그림처럼 각각의 좌표에는 고유의 값이 존재한다. 다음으로 MERGE 1 1 1 2 와 MERGE 2 2 2 3 을 실행해 보면 다음과 같다.
(1,1),(1,2)의 값을 동일하므로 같은 집합, 마찬가지로 (2,2),(2,3)의 값이 같으므로 같은 집합으로 생각하면 되요. 다음으로 MERGE 1 1 2 2를 실행한 결과를 보면 다음과 같다.
(1,1)의 고유값은 1이고, (2,2)의 고유값은 7입니다. 여기서 로직은 7값을 가진 모든 좌표를 찾아 1로 바꿔주면 되고 시간복잡도는 50 x 50= 2500번입니다.
지금까지 MERGE를 살펴보았고 제가 생각하기로 MERGE를 잘 구현할 수 있다면 위 문제를 스무스?하게 풀 수 있을거라 생각합니다.
const map = Array.from({ length : 51} , () => new Array(51).fill(null));
const parents = Array.from({ length : 51 } , () => new Array(51).fill(0));
for(let i=1; i<=50; i++){
for(let j=1; j<=50; j++){
parents[i][j] = i * 50 + j;
}
}
const update1 = (r,c,value) => {
//todo
//r,c와 병합된 다른 셀들의 값도 바꿔줘야함.
const p = parents[r][c];
for(let i=1; i<=50; i++){
for(let j=1; j<=50; j++){
if (parents[i][j] === p){
map[i][j] = value;
}
}
}
}
const update2 = (value1, value2) => {
for(let i=1; i<=50; i++){
for(let j=1; j<=50; j++){
if (map[i][j] === value1) map[i][j] = value2;
}
}
}
const merge = (r1, c1, r2, c2) => {
if (r1 === r2 && c1 === c2) return;
//두 셀의 최상위 조상의 셀이 같은지 확인
const aP = parents[r1][c1];
const bP = parents[r2][c2];
//최상위 조상이 같을 경우 패스
if (aP === bP) return;
//최상위 조상이 다를 경우
if ((map[r1][c1] !== null && map[r2][c2] !== null) || (map[r1][c1] !== null && map[r2][c2] === null)){
//(r2,c2)의 조상노드를 가지고 있는 모든 노드를 찾아 (r1,c1)값으로 변환
for(let i=1; i<=50; i++){
for(let j=1; j<=50; j++){
if (parents[i][j] === bP){
parents[i][j] = aP;
map[i][j] = map[r1][c1];
}
}
}
} else if (map[r1][c1] === null && map[r2][c2] !== null){
//(r1,c1)의 조상노드를 가지고 있는 모든 노드를 찾아 (r2,c2)값으로 변환
for(let i=1; i<=50; i++){
for(let j=1; j<=50; j++){
if (parents[i][j] === aP){
parents[i][j] = bP;
map[i][j] = map[r2][c2];
}
}
}
} else if (map[r1][c1] === null && map[r2][c2] === null){
for(let i=1; i<=50; i++){
for(let j=1; j<=50; j++){
if (parents[i][j] === aP){
parents[i][j] = bP;
}
}
}
}
}
const unmerge = (r,c) => {
//todo
const data = map[r][c];
//(r,c)의 최상위 조상을 찾는다
const p = parents[r][c];
//이 조상과 같은 모든 노드들의 조상값을 초기화시키고 null값으로 초기화
for(let i=1; i<=50; i++){
for(let j=1; j<=50; j++){
if (parents[i][j] === p){
parents[i][j] = 50 * i + j;
map[i][j] = null;
}
}
}
//(r,c)만 해체 전 셀 값을 가지고 있음
map[r][c] = data;
}
const print = (r,c) => {
if (map[r][c] === null) return "EMPTY";
return map[r][c];
}
function solution(commands) {
const answer = [];
for(let command of commands){
const splitCommand = command.split(' ');
const order = splitCommand[0];
if (order === 'UPDATE'){
const len = splitCommand.length;
//1. UPDATE r c value => update1
if (len === 4){
update1(Number(splitCommand[1]), Number(splitCommand[2]), splitCommand[3]);
}
//2. UPDATE value1 value2 => update2
else if (len === 3){
update2(splitCommand[1],splitCommand[2]);
}
}
//3. MERGE r1 c1 r2 c2
else if(order === 'MERGE'){
const r1 = Number(splitCommand[1]);
const c1 = Number(splitCommand[2]);
const r2 = Number(splitCommand[3]);
const c2 = Number(splitCommand[4]);
merge(r1,c1,r2,c2);
}
//4. UNMERGE r c
else if (order === 'UNMERGE'){
const r = Number(splitCommand[1]);
const c = Number(splitCommand[2]);
unmerge(r,c);
}
//5. PRINT r c
else if (order === 'PRINT'){
const r = Number(splitCommand[1]);
const c = Number(splitCommand[2]);
answer.push(print(r,c));
}
}
return answer;
}