표 병합
문제 링크 : 표 병합
문제 설명
당신은 표 편집 프로그램을 작성하고 있습니다.
표의 크기는 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 명령어를 실행하여 빈 셀에 값을 입력하는 예시입니다.
| 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가지 형태 중 하나입니다.
- "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 사이의 정수입니다.
- "UPDATE r c value"
- commands는 1개 이상의 "PRINT r c" 명령어를 포함하고 있습니다.
입출력 예
| commands | result |
|---|---|
| ["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"] |
풀이 방법
- 먼저 5가지의 명령어를 구분하기 위해
sstream을 활용해서 공백을 구분자로 두고, 처음의 문자열을 검사해서 동작을 구분했다.UPDATE의 경우에는 1번의 명령어는 뒤에 3개의 값, 2번의 명령어는 뒤에 2개의 값이 들어오기 때문에 마지막 값이 공백인 경우에는 2번, 공백이 아닌 경우에는 1번으로 구분해서 구현했다. - MERGE를 구현하는 방법에 있어서, 처음에는 병합을 관리하는 테이블을 따로 만들어서 각 셀마다 병합 정보를 모두 저장해두었다. 하지만 이러한 경우에 값을 업데이트하거나, 병합을 추가할 시에 병합된 모든 셀을 찾아다니면서 값을 업데이트해야 되니 시간초과가 발생했다.
- 따라서 MERGE를 구현하는 방법을 다른 방식으로 구현을 했다. 다른 방식으로는, 병합된 셀의 루트 노드를 설정을 해서, 그룹 대표 노드의 값만 저장하는 방식으로 구현하고자 했다. 해당 방식을 하는데에 있어서 2차원으로 값을 2개 관리하는 것보다는 하나만 관리하는 것이 편하기 때문에 각 셀마다 ID를 부여해서 1차원으로 테이블과 부모 노드를 관리했다.
string table[2501];
int parent[2501];
int getID(int r, int c){
return (r - 1) * 50 + (c - 1);
}
int findParent(int x){
if (parent[x] == x) return x;
parent[x] = findParent(parent[x]);
return parent[x];
}- "UPDATE r c value" : 루트 노드에 값을 저장
if(str == "UPDATE"){
string value1, value2, value;
ss >> value1 >> value2 >> value;
if (value != ""){
int r = stoi(value1), c = stoi(value2);
int id = getID(r, c);
int root = findParent(id);
table[root] = value;
}
...- "UPDATE value1 value2" : 루트 노드 중에 value1을 value2로 수정
if (str == "UPDATE"){
string value1, value2, value;
ss >> value1 >> value2 >> value;
if (value != ""){
...
}
else{
for(int i = 0; i <= 2500; i++){
int root = findParent(i);
if (parent[root] == root && table[root] == value1){
table[root] = value2;
}
}
}
}- "MERGE r1 c1 r2 c2" : 루트 노드를 확인하고, 셀 값에 따라 루트 노드를 덮어쓰기
else if(str == "MERGE"){
int r1, c1, r2, c2;
ss >> r1 >> c1 >> r2 >> c2;
int id1 = getID(r1, c1);
int id2 = getID(r2, c2);
id1 = findParent(id1);
id2 = findParent(id2);
if(id1 == id2) continue;
if (table[id1] == "" && table[id2] != ""){
parent[id1] = id2;
}else {
parent[id2] = id1;
}
}- "UNMERGE r c" : 해당 셀의 루트 노드를 확인한 후에 해당 루트 노드를 루트로 가지고 있는 모든 셀의 루트 노드를 초기화하고, 값을 비우기 => 기존의 값은 해당 셀에 넣기
else if(str == "UNMERGE"){
int r, c;
ss >> r >> c;
int id = getID(r, c);
int root = findParent(id);
string value = table[root];
vector<int> group;
for (int i = 0; i <= 2500; i++){
if (findParent(i) == root){
group.push_back(i);
}
}
for(int i : group){
parent[i] = i;
table[i] = "";
}
table[id] = value;
}- "PRINT r c" : 루트 노드에 값이 저장되어 있으면 해당 값을 반환, 안 되어 있으면 "EMPTY"
else if(str == "PRINT"){
int r, c;
ss >> r >> c;
int id = getID(r, c);
int root = findParent(id);
if(table[root] == ""){
answer.push_back("EMPTY");
}else{
answer.push_back(table[root]);
}
}-> 모든 명령어에 대해 O(N)의 시간복잡도를 가지고 N은 2,500, 명령어는 최대 1,000개이기 때문에 알맞은 알고리즘으로 보인다.
구현
#include <string>
#include <vector>
#include <sstream>
using namespace std;
string table[2501];
int parent[2501];
int getID(int r, int c){
return (r - 1) * 50 + (c - 1);
}
int findParent(int x){
if (parent[x] == x) return x;
parent[x] = findParent(parent[x]);
return parent[x];
}
vector<string> solution(vector<string> commands) {
vector<string> answer;
for(int i = 0; i <= 2500; i++){
table[i] = "";
parent[i] = i;
}
for(string command : commands){
stringstream ss;
string str;
ss.str(command);
ss >> str;
// 1. "UPDATE r c value" => (r, c) 값 : value
// 2. "UPDATE value1 value2" => value1 -> value2
// 3. "MERGE r1 c1 r2 c2" => (r1, c1) - (r2, c2)
// 4. "UNMERGE r c" => (r, c) 머지 해제 및 값 (r, c) 할당
// 5. "PRINT r c" => (r, c) 값 출력 (빈 경우 EMPTY)
if(str == "UPDATE"){
string value1, value2, value;
ss >> value1 >> value2 >> value;
if (value != ""){ // 1. "UPDATE r c value"
int r = stoi(value1), c = stoi(value2);
int id = getID(r, c);
int root = findParent(id);
table[root] = value;
}else{ // 2. "UPDATE value1 value2"
for(int i = 0; i <= 2500; i++){
int root = findParent(i);
if (parent[root] == root && table[root] == value1){
table[root] = value2;
}
}
}
}else if(str == "MERGE"){
int r1, c1, r2, c2;
ss >> r1 >> c1 >> r2 >> c2;
int id1 = getID(r1, c1);
int id2 = getID(r2, c2);
id1 = findParent(id1);
id2 = findParent(id2);
if(id1 == id2) continue;
if (table[id1] == "" && table[id2] != ""){
parent[id1] = id2;
}else {
parent[id2] = id1;
}
}else if(str == "UNMERGE"){
int r, c;
ss >> r >> c;
int id = getID(r, c);
int root = findParent(id);
string value = table[root];
vector<int> group;
for (int i = 0; i <= 2500; i++){
if (findParent(i) == root){
group.push_back(i);
}
}
for(int i : group){
parent[i] = i;
table[i] = "";
}
table[id] = value;
}else if(str == "PRINT"){
int r, c;
ss >> r >> c;
int id = getID(r, c);
int root = findParent(id);
if(table[root] == ""){
answer.push_back("EMPTY");
}else{
answer.push_back(table[root]);
}
}
}
return answer;
}
게임 개발자를 향해..