[C++] <2023 KAKAO BLIND RECRUITMENT> 표 병합

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/150366

 

문제 3줄 요약

1. 표 편집 프로그램 작성 중 (50 X 50)

2. UPDATE, MERGE, UNMERGE, PRINT 기능 존재

3. 명령어 출력 결과를 구하라

---

 

문제에 제시되어 있는 기능은 총 4개이다.

 

Update, Merge, Unmerge, Print

 

update와 print는 구현에 어려움이 없지만,

merge와 unmerge 부분에 있어 단순 구현으로는 구하기 힘들다는 생각이 들었다.

 

 

 

셀을 병합하고 병합 해제하는 과정에서

값을 가지고 있는 셀(부모)를 찾는 것이 중요한 포인트라고 생각하였고

Union-Find를 사용하여 접근하였다.

 

함수를 하나씩 구현해보자.

 

---

 

pair<int, int> findParent(int r, int c){
    if (make_pair(r, c) == merge_table[r][c]) return make_pair(r, c);
    return findParent(merge_table[r][c].first, merge_table[r][c].second);
}

 

 

기능 구현에 앞서

해당 좌표 (r, c)에 대한 pair 값이 자신의 좌표가 아니라면,

값을 가지고 있는 부모 셀의 좌표를 찾는 findParent 함수를 작성하였다.

 

각 함수마다

좌표에 대한 부모 셀 좌표를 찾을 때 사용할 것이다.

 

 

---

 

void update(int r, int c, string value){
    tie(r, c) = findParent(r, c);
    table[r][c] = value;
    return;
}

 

인자로 받은 (r, c) 좌표에

바로 값을 업데이트하는 것이 아닌

실질적으로 병합되어 값을 들고 있는 부모 셀의 값을 업데이트 해줬다.

 

---

 

// merge - unmerge 과정에서 union-find가 필요하다고 생각.
void merge(int r1, int c1, int r2, int c2){
    tie(r1, c1) = findParent(r1, c1);
    tie(r2, c2) = findParent(r2, c2);
    
    if(r1==r2 && c1==c2) return;
    string value1 = table[r1][c1], value2 = table[r2][c2];
    
    // 우측 좌표에만 값이 있을 경우 -> 부모가 오른쪽
    if(value1.empty() && !value2.empty()) {
        merge_table[r1][c1] = make_pair(r2, c2);
        
        for(int i=1; i<=50; i++) for(int j=1; j<=50; j++) // 바뀐 부모의 자식들도 변경
            if(merge_table[i][j] == make_pair(r1, c1)) merge_table[i][j] = make_pair(r2, c2);
    }
    else { // 그 외의 경우 -> 부모가 왼쪽
        merge_table[r2][c2] = make_pair(r1, c1);
        table[r2][c2].clear();
        
        for(int i=1; i<=50; i++) for(int j=1; j<=50; j++) // 바뀐 부모의 자식들도 변경
            if(merge_table[i][j] == make_pair(r2, c2)) merge_table[i][j] = make_pair(r1, c1);
    }
    return;
}

 

 

merge에는 다음과 같은 조건이 있다.

 

1. 두 좌표만 영향

2. 위치가 같다면 셀을 무시 (부모 셀이 같아도 동일)

3. 한 셀만 값이 있다면 그 값으로 병합

4. 두 셀 모두 값이 있다면 (r1, c1)의 셀 값으로 병합

 

따라서 (r2, c2) 셀에만 값이 있는 경우를 제외하곤

모두 (r1, c1)을 부모로 설정해주었다.

 

 

(r1, c1) → (r2, c2) 밑으로 들어가는 경우,

(r2, c2) → (r1, c1) 밑으로 들어가는 경우

모두 결국 자식으로 들어간 좌표를 부모로 삼고 있던 좌표 또한 갱신이 필요하다.

 

---

 

 

void unmerge(int r, int c){
    int r1 = r, c1 = c;
    tie(r1, c1) = findParent(r, c);
    string value = table[r1][c1];
    
    for(int i=1; i<=50; i++) for(int j=1; j<=50; j++)
        if(merge_table[i][j] == make_pair(r1, c1)) {
            merge_table[i][j] = make_pair(i, j);
            table[i][j].clear(); // 병합 해제 후 해당 좌표 외의 값 삭제
        }
    
    table[r][c] = value;
    return;
}

 

 

 

병합을 해제할 때에는

병합 되었던 셀의 값들은 초기화 시켜주고

해제 전 가지고 있던 값이 있다면 (r, c) 위치에 값을 대입 해주면 된다.

 

---

 

 

void print(int r, int c){
    tie(r, c) = findParent(r, c);
    string value = table[r][c];
    
    if(!value.empty()) answer.push_back(table[r][c]);
    else answer.push_back("EMPTY");
    return;
}

 

 

해당 좌표에 부모 셀이 값을 가지고 있다면

해당 값을 넣어주고

그렇지 않다면 "EMPTY"를 넣어주면 된다.

 

---

 

최종 코드

#include <string>
#include <vector>
#include <tuple>
#include <iostream>

using namespace std;

string table[51][51];
pair<int, int> merge_table[51][51];
vector<string> answer;

vector<string> split(string input, string delimiter) {
	vector<string> ret;
	long long 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.length());
	}
	ret.push_back(input);
	return ret;
}

pair<int, int> findParent(int r, int c){
    if (make_pair(r, c) == merge_table[r][c]) return make_pair(r, c);
    return findParent(merge_table[r][c].first, merge_table[r][c].second);
}

void update(int r, int c, string value){
    tie(r, c) = findParent(r, c);
    table[r][c] = value;
    return;
}

// merge - unmerge 과정에서 union-find가 필요하다고 생각.
void merge(int r1, int c1, int r2, int c2){
    tie(r1, c1) = findParent(r1, c1);
    tie(r2, c2) = findParent(r2, c2);
    
    if(r1==r2 && c1==c2) return;
    string value1 = table[r1][c1], value2 = table[r2][c2];
    
    // 우측 좌표에만 값이 있을 경우 -> 부모가 오른쪽
    if(value1.empty() && !value2.empty()) {
        merge_table[r1][c1] = make_pair(r2, c2);
        
        for(int i=1; i<=50; i++) for(int j=1; j<=50; j++) // 바뀐 부모의 자식들도 변경
            if(merge_table[i][j] == make_pair(r1, c1)) merge_table[i][j] = make_pair(r2, c2);
    }
    else { // 그 외의 경우 -> 부모가 왼쪽
        merge_table[r2][c2] = make_pair(r1, c1);
        table[r2][c2].clear();
        
        for(int i=1; i<=50; i++) for(int j=1; j<=50; j++) // 바뀐 부모의 자식들도 변경
            if(merge_table[i][j] == make_pair(r2, c2)) merge_table[i][j] = make_pair(r1, c1);
    }
    return;
}

void unmerge(int r, int c){
    int r1 = r, c1 = c;
    tie(r1, c1) = findParent(r, c);
    string value = table[r1][c1];
    
    for(int i=1; i<=50; i++) for(int j=1; j<=50; j++)
        if(merge_table[i][j] == make_pair(r1, c1)) {
            merge_table[i][j] = make_pair(i, j);
            table[i][j].clear(); // 병합 해제 후 해당 좌표 외의 값 삭제
        }
    
    table[r][c] = value;
    return;
}

void print(int r, int c){
    tie(r, c) = findParent(r, c);
    string value = table[r][c];
    
    if(!value.empty()) answer.push_back(table[r][c]);
    else answer.push_back("EMPTY");
    return;
}

vector<string> solution(vector<string> commands) {
    for(int i=1; i<=50; i++) for(int j=1; j<=50; j++) merge_table[i][j] = {i, j};
    
    for(string s : commands){
        vector<string> cmd = split(s, " ");
        
        if(cmd[0] == "UPDATE"){
            if(cmd.size() > 3) update(stoi(cmd[1]), stoi(cmd[2]), cmd[3]);
            else{
                for(int i=1; i<=50; i++) for(int j=1; j<=50; j++)
                    if(table[i][j] == cmd[1]) update(i, j, cmd[2]);
            }
        }
        
        if(cmd[0] == "MERGE"){
            int r1 = stoi(cmd[1]), c1 = stoi(cmd[2]), r2 = stoi(cmd[3]), c2 = stoi(cmd[4]);
            merge(r1,c1,r2,c2);   
        }
        
        if(cmd[0] == "UNMERGE"){
            int r = stoi(cmd[1]), c = stoi(cmd[2]);
            unmerge(r,c);
        }
        
        if(cmd[0] == "PRINT"){
            int r = stoi(cmd[1]), c = stoi(cmd[2]);
            print(r,c);
        }
    }
    
    return answer;
}

 

아직까지 코딩테스트를 치루면서

union-find 문제를 출제한걸 만나보진 못했는데,

주어진 조건과 시간복잡도를 고려해서 접근한다면 풀 수 있을 것 같다.

 

근데 좀 푸는데 오래걸리는 듯..