[PS] 백준 10630번: RLE Replacement

RLE Replacement

R 1 L 2 E 1 $
L 1 $
A 1 $

이 경우, R1 L1 A1 E1가 아니고 R1 A1 L1 E1가 되어야 한다는걸 눈치를 못채서 꽤 오래 걸렸다.

#include <bits/stdc++.h>

#define endl "\n"
#define pci pair<char, int>

using namespace std;

vector<pci> A;
vector<pci> B;
vector<pci> C;

void manage_input(vector<pci>& v) {
	while (true) {
		char c; cin >> c;
		if (c == '$') break;
		int n; cin >> n;
		v.push_back(make_pair(c, n));
	}
}

void delete_zero(vector<pci>& v) {
	bool changed = true;
	while (changed) {
		changed = false;
		for (int i = 0; i < int(v.size()); i++) {
			if (v[i].second == 0) {
				v.erase(v.begin() + i);
				changed = true;
				break;
			}
		}
	}
}

void merge(vector<pci>& v) {
	bool changed = true;
	while (changed) {
		changed = false;
		for (int i = 0; i < int(v.size()) - 1; i++) {
			if (v[i].first == v[i + 1].first) {
				v[i].second += v[i + 1].second;
				v.erase(v.begin() + i + 1);
				changed = true;
				break;
			}
		}
	}
}

int main() {
	manage_input(A), manage_input(B), manage_input(C);
	int asize = A.size(), bsize = B.size(), csize = C.size();

	int b_startidx_in_a = -1;
	for (int i = 0; i < asize - bsize + 1; i++) {
		bool flag = true;
		for (int j = 0; j < bsize; j++) {
			char achar, bchar; int anum, bnum;
			tie(achar, anum) = A[i + j], tie(bchar, bnum) = B[j];

			if (achar != bchar) { flag = false; break; }

			if (j == 0 || j == (bsize - 1)) {
				if (anum < bnum) { flag = false; break; }
			}
			else {
				if (anum != bnum) { flag = false; break; }
			}
		}

		if (flag == true) {
			b_startidx_in_a = i;
			break;
		}
	}

	if (b_startidx_in_a == -1) {
		for (auto& p : A) cout << p.first << " " << p.second << " ";
		cout << "$" << endl;
		return 0;
	}

	vector<pci> ansvec;
	int b_lastidx_in_a = b_startidx_in_a + int(bsize) - 1;
	for (int i = 0; i < b_startidx_in_a; i++) { ansvec.push_back(A[i]); }

	if (bsize > 1) {	
		for (int i = b_startidx_in_a, j = 0; j < bsize - 1; i++, j++)
			ansvec.push_back(make_pair(A[i].first, A[i].second - B[j].second));
		for (int i = 0; i < csize; i++) { ansvec.push_back(C[i]); }
		ansvec.push_back(make_pair(A[b_lastidx_in_a].first, A[b_lastidx_in_a].second - B.back().second));
	}
	else {
		for (int i = 0; i < csize; i++) { ansvec.push_back(C[i]); }
		ansvec.push_back(make_pair(A[b_startidx_in_a].first, A[b_startidx_in_a].second - B[0].second));
	}

	if (b_lastidx_in_a + 1 < asize) {
		for (int i = b_lastidx_in_a + 1; i < asize; i++) {
			ansvec.push_back(A[i]);
		}
	}

	delete_zero(ansvec);
	merge(ansvec);

	for (auto& p : ansvec)  cout << p.first << " " << p.second << " ";
	cout << "$" << endl;

	return 0;
}