표 병합

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

문제 설명

당신은 표 편집 프로그램을 작성하고 있습니다.

표의 크기는 50 × 50으로 고정되어있고 초기에 모든 셀은 비어 있습니다.

각 셀은 문자열 값을 가질 수 있고, 다른 셀과 병합될 수 있습니다.

위에서 r번째, 왼쪽에서 c번째 위치를 (r, c)라고 표현할 때, 당신은 다음 명령어들에 대한 기능을 구현하려고 합니다.

1. "UPDATE r c value"
   • (r, c) 위치의 셀을 선택합니다.
   • 선택한 셀의 값을 value로 바꿉니다.
2. "UPDATE value1 value2"
   • value1을 값으로 가지고 있는 모든 셀을 선택합니다.
   • 선택한 셀의 값을 value2로 바꿉니다.
3. "MERGE r1 c1 r2 c2"
   • (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀을 선택하여 병합합니다.
   • 선택한 두 위치의 셀이 같은 셀일 경우 무시합니다.
   • 선택한 두 셀은 서로 인접하지 않을 수도 있습니다. 이 경우 (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀만 영향을 받으며,
     그 사이에 위치한 셀들은 영향을 받지 않습니다.
   • 두 셀 중 한 셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지게 됩니다.
   • 두 셀 모두 값을 가지고 있을 경우 병합된 셀은 (r1, c1) 위치의 셀 값을 가지게 됩니다.
   • 이후 (r1, c1) 와 (r2, c2) 중 어느 위치를 선택하여도 병합된 셀로 접근합니다.
4. "UNMERGE r c"
   • (r, c) 위치의 셀을 선택하여 해당 셀의 모든 병합을 해제합니다.
   • 선택한 셀이 포함하고 있던 모든 셀은 프로그램 실행 초기의 상태로 돌아갑니다.
   • 병합을 해제하기 전 셀이 값을 가지고 있었을 경우 (r, c) 위치의 셀이 그 값을 가지게 됩니다.
5. "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가지 형태 중 하나입니다.
  1. "UPDATE r c value"
     • r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
     • value는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
  2. "UPDATE value1 value2"
     • value1은 선택할 셀의 값, value2는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
  3. "MERGE r1 c1 r2 c2"
     • r1, c1, r2, c2는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
  4. "UNMERGE r c"
     • r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
  5. "PRINT r c"
     • r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
• 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"]

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다. (1,3) 위치의 셀은 비어있고 (1,4) 위치의 셀 값은 "group"입니다.
  따라서 ["EMPTY", "group"]을 return 해야 합니다.

입출력 예 #2

• 모든 UPDATE 명령어를 실행하면 아래와 같은 상태가 됩니다.

• "MERGE 1 1 1 2" 명령어를 실행하면 아래와 같은 상태가 됩니다.

• "MERGE 2 2 2 1" 명령어를 실행하면 아래와 같은 상태가 됩니다.

• "MERGE 2 1 1 1" 명령어를 실행하면 아래와 같은 상태가 됩니다.

• "UNMERGE 2 2" 명령어를 실행하면 아래와 같은 상태가 됩니다.

---

통과된 코드

#include <string>
#include <vector>
#include <sstream>
#include <cstdlib>
#include <map>

using namespace std;

string _StrArr[51][51];
string* _PtrArr[51][51];
pair<int, int> _MergeArr[51][51];
map<pair<int, int>, vector<pair<int, int>>> _MergeMap;
vector<string> _Answer;

void CommandProcessing(string& _command)
{
	istringstream iss(_command);
	string buffer;
	vector<string> res;
	while (getline(iss, buffer, ' '))
		res.push_back(buffer);

	if (res[0] == "UPDATE") {
		if (res.size() > 3) {  // "UPDATE r c value"
			pair<int, int> _MPair = _MergeArr[atoi(res[1].c_str())][atoi(res[2].c_str())];
			*_PtrArr[_MPair.first][_MPair.second] = res[3];
		}
		else {	// "UPDATE value1 value2"
			for (int i = 1; i <= 50; i++)
				for (int j = 1; j <= 50; j++) {
					if (_StrArr[i][j] == "" || _StrArr[i][j] != res[1])
						continue;
					_StrArr[i][j] = res[2];
				}
		}
	}
	else if (res[0] == "MERGE") { // "UNMERGE r c"
		// 같은 좌표일 경우 넘어간다.
		if (res[1] == res[3] && res[2] == res[4])
			return;

		pair<int, int> _MPair = _MergeArr[atoi(res[1].c_str())][atoi(res[2].c_str())];
		pair<int, int> _TPair = _MergeArr[atoi(res[3].c_str())][atoi(res[4].c_str())];

		// 같은 좌표를 가르키고 있으면 넘어간다.
		if (_MPair == _TPair) 
			return;

		auto _Main = _MergeMap.find(_MPair);
		auto _Target = _MergeMap.find(_TPair);
		if (_Main == _MergeMap.end()) {
			vector<pair<int, int>> _Temp;
			_MergeMap.insert({ _MPair, _Temp });
			_Main = _MergeMap.find(_MPair);
		}

		_Main->second.push_back(_TPair);

		if (*_PtrArr[_MPair.first][_MPair.second] == "" && *_PtrArr[_TPair.first][_TPair.second] != "") {
			*_PtrArr[_MPair.first][_MPair.second] = "";
			_PtrArr[_MPair.first][_MPair.second] = _PtrArr[_TPair.first][_TPair.second];
			for (auto& it : _Main->second)
				_PtrArr[it.first][it.second] = _PtrArr[_TPair.first][_TPair.second];
		}

		_PtrArr[_TPair.first][_TPair.second] = _PtrArr[_MPair.first][_MPair.second];
		_MergeArr[_TPair.first][_TPair.second] = _MPair;

		if (_Target != _MergeMap.end()) {
			for (auto& it : _Target->second) {
				_Main->second.push_back(it);
				_MergeArr[it.first][it.second] = _MPair;
				_PtrArr[it.first][it.second] = _PtrArr[_MPair.first][_MPair.second];
			}
			_MergeMap.erase(_Target);
		}
	}
	else if (res[0] == "UNMERGE") { // "UNMERGE r c"
		pair<int, int> _MPair = _MergeArr[atoi(res[1].c_str())][atoi(res[2].c_str())];
		string str = *_PtrArr[_MPair.first][_MPair.second];
		_MergeArr[_MPair.first][_MPair.second] = _MPair;
		_PtrArr[_MPair.first][_MPair.second] = &_StrArr[_MPair.first][_MPair.second];
		*_PtrArr[_MPair.first][_MPair.second] = "";

		auto _Main = _MergeMap.find(_MPair);
		if (_Main != _MergeMap.end()) {
			for (auto& it : _Main->second) {
				_MergeArr[it.first][it.second] = make_pair(it.first, it.second);
				_PtrArr[it.first][it.second] = &_StrArr[it.first][it.second];
				*_PtrArr[it.first][it.second] = "";
			}
			_MergeMap.erase(_Main);
		}
		_StrArr[atoi(res[1].c_str())][atoi(res[2].c_str())] = str;
	}
	else {// "PRINT r c"
		pair<int, int> _MPair = _MergeArr[atoi(res[1].c_str())][atoi(res[2].c_str())];
		string str = *_PtrArr[_MPair.first][_MPair.second];
		if (str == "") _Answer.push_back("EMPTY");
		else _Answer.push_back(str);
	}
}


vector<string> solution(vector<string> commands) {
	// 포인터 배열 초기화
	for (int i = 1; i <= 50; i++)
		for (int j = 1; j <= 50; j++) {
			_PtrArr[i][j] = &_StrArr[i][j];
			_MergeArr[i][j] = make_pair(i, j);
			_StrArr[i][j] = "";
		}

	// 명령어 처리
	for (auto& it : commands)
		CommandProcessing(it);
	
	return _Answer;
}

추가 반례

예제 입력 1

["UPDATE 1 1 menu", "MERGE 1 1 1 2", "MERGE 1 1 1 3", "MERGE 1 1 1 4", "MERGE 1 2 1 3", "UPDATE 1 1 hansik", "PRINT 1 1", "PRINT 1 2", "PRINT 1 3", "PRINT 1 4"]

예제 출력 1

["hansik", "hansik", "hansik", "hansik"]

예제 입력 2

["MERGE 1 1 2 2", "UPDATE 1 1 A", "UNMERGE 1 1", "PRINT 1 1", "PRINT 2 2"]

예제 출력 2

["A", "EMPTY"]

예제 입력 3

["UPDATE 1 1 A", "UPDATE 2 2 B", "UPDATE 3 3 C", "UPDATE 4 4 D", "MERGE 1 1 2 2", "MERGE 3 3 4 4", "MERGE 1 1 4 4", "UNMERGE 3 3", "PRINT 1 1", "PRINT 2 2", "PRINT 3 3", "PRINT 4 4"]

예제 출력 3

["EMPTY", "EMPTY", "A", "EMPTY"]

예제 입력 4

["UPDATE 1 1 1", "UPDATE 1 2 2", "UPDATE 2 1 3", "UPDATE 2 2 4", "MERGE 1 1 1 2", "MERGE 2 2 2 1", "MERGE 2 1 1 1", "PRINT 1 1", "UNMERGE 2 2", "PRINT 1 1"]

예제 출력 4

["4", "EMPTY"]