문제
풀이
입력 받은 명령어 문자열을 " "를 기준으로 나눈 뒤 명령어에 따라 다른 switch-case문을 작성한다.
- C++에서 switch 문에
string을 사용할 수 없다는 것을 처음 알게 되었다.
표 병합과 관련된 명령어 처리는 union find 알고리즘을 활용하여 해결했다.
struct cell {
int ptr;
string value="EMPTY";
};
int find(int x, vector<cell>& table){
if (table[x].ptr == x){
return x;
}
else{
return table[x].ptr = find(table[x].ptr, table);
}
}
void merge(int x, int y, vector<cell>& table){
x = find(x, table);
y = find(y, table);
if (table[x].value == "EMPTY" && table[y].value != "EMPTY"){
table[x].ptr = y;
}
else{
table[y].ptr = x;
}
}각 셀이 가리키는 셀 (ptr), 셀의 값(value)로 구성된 구조체 cell을 선언하였다.
- 모든
cell에 접근할 때find()함수를 통해 항상 root로 접근한다. - union은 문제에 적힌 제한 사항에 유의하여 작성한다.
- union 알고리즘에서 따로 최적화는 진행하지 않았다.
표의 셀 좌표를 1차원으로 변경하여 union find 알고리즘으로 접근하기 편하게 만들었다.
vector<cell> table(50 * 50);
for (int i=0; i < 50 * 50; ++i){
table[i].ptr = i;
}ptr속성은 자신의 셀 위치로 초기화 하였다.
UPDATE
두 가지 경우로 나뉜다.
1. "UPDATE value1 value2"
- 표 전체를 순회하며
value1의 값을 가진 모든cell을value2로 바꾼다.
"UPDATE r c value"
r,c셀이 최종으로 가리키는 rootcell의value를value1으로 변경한다.
MERGE
union 알고리즘 그 자체이지만 문제의 제한 사항을 따라야 한다.
- "
r1,c1셀이 비어있고,r2,c2셀에 값이 들어 있는 경우 "와 그 외의 경우를 나눠서 처리해야 한다. r1c1셀의 값이r2c2에 저장된다면r2c2가r1c1을 가리켜야 한다.
UNMERGE
rc셀을 find()하여 root 셀을 알아낸 뒤 모든 표를 순회하며 각 셀에 대해 find()하여 rc셀의 root와 비교한다.
같다면 병합된 셀이므로 ptr을 자신의 위치로, value 를 "EMPTY"
로 초기화한다.
이때 주의해야 할 것은 병합되어 있는 셀을 모두 찾은 뒤, 각 셀의ptr, value값을 초기화해야 한다.
그렇지 않고 병합된 셀을 찾을 때마다 cell의 속성값을 초기화하면 연결고리가 끊겨서 병합된 모든 셀을 찾을 수 없는 경우가 발생한다.
find로 찾은 root 셀을 answer에 저장한다.
코드
#include <string>
#include <vector>
#include <map>
using namespace std;
struct cell {
int ptr;
string value="EMPTY";
};
enum Command{
UPDATE,
MERGE,
UNMERGE,
PRINT
};
vector<string> split(string input, string delimiter) {
vector<string> ret;
size_t pos = 0;
string token = "";
while ((pos = input.find(delimiter)) != string::npos){
token = input.substr(0, pos);
ret.push_back(token);
input.erase(0, pos + delimiter.size());
}
ret.push_back(input);
return ret;
}
int find(int x, vector<cell>& table){
if (table[x].ptr == x){
return x;
}
else{
return table[x].ptr = find(table[x].ptr, table);
}
}
void merge(int x, int y, vector<cell>& table){ // union은 c++에서 예약어로 이미 있네?
x = find(x, table);
y = find(y, table);
if (table[x].value == "EMPTY" && table[y].value != "EMPTY"){
table[x].ptr = y;
}
else{
table[y].ptr = x;
}
}
vector<string> solution(vector<string> commands) {
vector<string> answer;
// 테이블 초기화
vector<cell> table(50 * 50);
for (int i=0; i < 50 * 50; ++i){
table[i].ptr = i;
}
map<string, int> commandNum;
commandNum["UPDATE"] = UPDATE;
commandNum["MERGE"] = MERGE;
commandNum["UNMERGE"] = UNMERGE;
commandNum["PRINT"] = PRINT;
for (string i: commands){
vector<string> line;
line = split(i, " ");
string command = line[0];
int r1;
int c1;
int r2;
int c2;
string value1;
string value2;
// map과 enum의 조합으로 switch 문을 작성하면 나중에 유지보수 할 때 매우매우 귀찮아 진다
// command가 하나라도 늘어난다면 map, enum 초기화부분 수정과 case 추가를 매번 하드코딩으로 해야하기 때문이다.
switch (commandNum[command]){
case UPDATE:{
if (line.size() == 3) { // "UPDATE value1 value2"
value1 = line[1];
value2 = line[2];
for (auto& i: table){
if (i.value == value1)
i.value = value2;
}
}
else{ // UPDATE r c value
r1 = stoi(line[1])-1;
c1 = stoi(line[2])-1;
value1 = line[3];
int idx = r1 * 50 + c1;
table[find(idx, table)].value = value1;
}
break;
}
case MERGE:{
r1 = stoi(line[1])-1;
c1 = stoi(line[2])-1;
c2 = stoi(line[4])-1;
r2 = stoi(line[3])-1;
merge(r1 * 50 + c1, r2 * 50 + c2, table);
break;
}
case UNMERGE:{
r1 = stoi(line[1])-1;
c1 = stoi(line[2])-1;
int idx = r1 * 50 + c1;
int root = find(idx, table);
value1 = table[root].value;
vector<int> target;
for (int i=0; i < 50 * 50; ++i){
if (table[find(i, table)].ptr == root){
target.push_back(i);
}
}
for (int i: target){
table[i].value = "EMPTY";
table[i].ptr = i;
}
table[idx].value = value1;
break;
}
case PRINT:{
r1 = stoi(line[1])-1;
c1 = stoi(line[2])-1;
string res = table[find(r1 * 50 + c1, table)].value;
answer.push_back(res);
break;
}
default:
break;
}
}
return answer;
}c++에서 swtich 문으로 string을 사용할 수 없다는 것을 알게 되고 이와 이렇게 된거 enum을 이용하여 구현해보았으나 큰 장점을 느낄 수 없었다.
if () else if()로 작성하는것이 더 좋았을 것 같다.
붉은다리 제프