-
[PS] 백준 10630번: RLE Replacement문제해결 2023. 10. 25. 17:18
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; }
'문제해결' 카테고리의 다른 글
[PS] 코드트리: 싸움땅 (0) 2023.10.25 [PS] 코드트리: 코드트리 빵 (0) 2023.10.25 [PS] 백준 1005번: ACM Craft (0) 2023.10.25 [PS] 백준 21610번: 마법사 상어와 비바라기 (0) 2023.10.25 [PS] 백준 12865번: 평범한 배낭 (0) 2023.10.25