프로그래머스 문제 - 표 병합

프로그래머스 표 병합 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

50 X 50으로 고정된 표의 편집 프로그램을 작성해야 합니다.

"PRINT r c"명령어에 대한 실행결과를 순서대로 출력해야 합니다.

문제 풀이

엑셀과 비슷한 표 편집 프로그램을 만들어내는 문제입니다.
UPDATE나 PRINT같은 데이터를 넣고 출력하는 부분은 문제가 되지 않지만 MERGE와 UNMERGE인 병합과 병합 해제를 작성하는 것이 꽤나 어렵습니다.

MERGE를 진행하면 MERGE한 셀끼리의 값은 동일하며, UNMERGE가 진행되면 연결되어 있는 모든 셀들이 전부 나눠집니다.
즉, MERGE가 진행된 셀들은 어떤 셀과 MERGE가 진행되었는지 알아야 UNMERGE가 가능해집니다.
배열로 셀의 위치들을 저장할 수 있지만 실행시간을 줄이기 위해 Union Find 알고리즘을 사용하였습니다.

MERGE가 이루어지면 진행시킬 두 셀의 좌표가 주어지게 되는데, 두 셀중 한 곳의 셀에 값이 저장되게 됩니다.
그러면 값이 저장되지 않는 셀에 값이 저장된 셀의 좌표를 같이 저장해준 후 나중에 값이 저장되지 않는 셀을 불러오면 저장해둔 셀에 있는 값을 불러와주면 됩니다.
UNMERGE도 똑같이 주어진 좌표의 저장해둔 셀의 좌표를 들고 모든 셀을 검색하여 셀들이 저장해둔 좌표가 같다면 MERGE가 이루어진 셀이기 때문에 해제 작업을 진행시켜주면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<string> split(string input, char dlim)
{
	vector<string> result;

	stringstream ss;
	string stringBuffer;
	ss.str(input);
	
	while (getline(ss, stringBuffer, dlim))	
	{
		result.push_back(stringBuffer);
	}

	return result;
}

vector<string> solution(vector<string> commands) {
    vector<string> answer;
    vector<vector<pair<string, pair<int, int>>>> tableMap(51, vector<pair<string, pair<int, int>>>(51));
    
    //테이블의 기본값 설정
    for(int i = 1; i <= 50; i++)
    {
        for(int j = 1; j <= 50; j++)
        {
            tableMap[i][j].first = "";
            tableMap[i][j].second = make_pair(i, j);
        }
    }
    for(string str : commands)
    {
        vector<string> result = split(str, ' ');    //" "를 기준으로 문자열을 나눠줌
        if(result[0][0] == 'U' && result[0][1] == 'P'){
            if(result.size() == 4){ //단어를 셀 위치에 넣어줌
                int x = stoi(result[1]);
                int y = stoi(result[2]);
                //병합된 셀일 경우 답을 적어둔 셀 위치에 값을 넣어줌
                pair<int, int> p = make_pair(tableMap[x][y].second.first, tableMap[x][y].second.second);
                tableMap[x][y].first = result[3];
                tableMap[p.first][p.second].first = result[3];
            }else{  //주어진 단어와 같은 단어들을 전부 변환
                for(int i = 1; i <= 50; i++)
                {
                    for(int j = 1; j <= 50; j++)
                    {
                        if(tableMap[i][j].first == result[1])
                            tableMap[i][j].first = result[2];
                    }
                }
            }
        }else if(result[0][0] == 'M'){  //셀끼리 합침
            int x1 = stoi(result[1]);
            int y1 = stoi(result[2]);
            int x2 = stoi(result[3]);
            int y2 = stoi(result[4]);
            if(x1 == x2 && y1 == y2)    //두 좌표가 같으면 무시
                continue;
            pair<int, int> p;
            pair<int, int> changePair;
            
            //병합한 모든 셀들의 값은 첫 번째 좌표에 있는 값으로 통일시킴
            //만약 두 번째 좌표에만 값이 있을 시 두 번째 값으로 통일시킴
            //병합된 것을 알기 위해 값으로 통일시킨 값의 셀 위치를 각각 저장시킴
            string s;
            if(tableMap[x1][y1].first == "" && tableMap[x2][y2].first != "")
            {    
                p = make_pair(tableMap[x2][y2].second.first, tableMap[x2][y2].second.second);
                changePair = make_pair(tableMap[x1][y1].second.first, tableMap[x1][y1].second.second);
            }else{
                p = make_pair(tableMap[x1][y1].second.first, tableMap[x1][y1].second.second);
                changePair = make_pair(tableMap[x2][y2].second.first, tableMap[x2][y2].second.second);
            }
            
            for(int i = 1; i <= 50; i++)
            {
                for(int j = 1; j <= 50; j++)
                {
                    if(tableMap[i][j].second.first == changePair.first && tableMap[i][j].second.second == changePair.second)
                    {
                        tableMap[i][j].second = p;
                        tableMap[i][j].first = tableMap[p.first][p.second].first;
                    }
                }
            }
            
        }else if(result[0][0] == 'U' && result[0][1] == 'N'){   //병합된 셀 해제
            int x = stoi(result[1]);
            int y = stoi(result[2]);
            pair<int, int> p = tableMap[x][y].second;
            string s = tableMap[p.first][p.second].first;
            //지금 위치의 셀에서 저장해준 병합된 셀의 위치와 같은 모든 셀들을 전부 해제시킴
            //값은 지금 위치의 셀에 저장
            for(int i = 1; i <= 50; i++)
            {
                for(int j = 1; j <= 50; j++)
                {
                    if(tableMap[i][j].second.first == p.first && tableMap[i][j].second.second == p.second)
                    {
                        tableMap[i][j].first = "";
                        tableMap[i][j].second = make_pair(i, j);
                    }
                }
            }
            tableMap[x][y].first = s;
        }else if(result[0][0] == 'P'){  //값 출력
            int x = stoi(result[1]);
            int y = stoi(result[2]);
            if(tableMap[tableMap[x][y].second.first][tableMap[x][y].second.second].first == "")
                answer.push_back("EMPTY");
            else
                answer.push_back(tableMap[tableMap[x][y].second.first][tableMap[x][y].second.second].first);
        }
    }
    
    return answer;
}

출저

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