알고리즘 공부
백준 볼 모으기
컴퓨터과학
2023. 8. 4. 19:28
https://www.acmicpc.net/problem/17615
17615번: 볼 모으기
첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주
www.acmicpc.net
뭔가 이제 그리드 알고리즘에 익숙해진건지 문제가 쉬운건지 흐음
#include <iostream>
#include <vector>
#include <queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<map>
#include<stack>
using namespace std;
struct Point {
int i, j, t, cnt, power;
char c;
};
void Prints(vector<vector<int>>maps, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<bool>>maps, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<char>>maps, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[i][j];
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<vector<char>>>maps, int n, int m, int k) {
for (int t = 0; t < k; t++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[t][i][j];
}
cout << endl;
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<vector<bool>>>maps, int n, int m, int k) {
for (int t = 0; t < k; t++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[t][i][j];
}
cout << endl;
}
cout << endl;
}
cout << endl;
}
void Prints(vector<int>line, int n) {
for (int i = 0; i < n; i++) {
cout << line[i] << ",";
}
cout << endl;
}
void Prints(string str, int n) {
for (int i = 0; i < n; i++) {
cout << str[i] << ",";
}
cout << endl;
}
bool checkmaps(vector<vector<int>>maps, vector<vector<int>>anw, int n, int m) {
bool bCheck = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maps[i][j] != anw[i][j]) {
bCheck = true;
i = n + 1;
j = m + 1;
continue;
}
}
}
return bCheck;
}
bool findstart(vector<vector<int>>maps, vector<vector<int>>anw, int n, int m, int) {
bool bCheck = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maps[i][j] != anw[i][j]) {
bCheck = true;
i = n + 1;
j = m + 1;
continue;
}
}
}
return bCheck;
}
struct Data {
int index;
string times;
};
int main() {
long long n;
cin >> n;
string balls;
cin >> balls;
string balls1=balls;
string balls2=balls;
string balls3 = balls;
string balls4 = balls;
long long pblueRight = 0;
long long predRight = 0;
long long pblueleft = n-1;
long long predleft = n - 1;
char pivotb = 'B';
char pivotr = 'R';
vector<long long>gCnt;
long long brcnt = 0;
long long blcnt = 0;
long long rrcnt = 0;
long long rlcnt = 0;
for (long long i = 0; i < n; i++)
{
//blue인경우
//blue 왼쪽으로 모으기
//순방향
if (balls1[i] == pivotb) {
if (balls1[i] == balls1[pblueRight]) {
pblueRight++;
}
else {
int tmp = balls1[pblueRight];
balls1[pblueRight] = balls1[i];
balls1[i] = tmp;
pblueRight++;
brcnt++;
//cout << balls1 <<endl;
}
}
//Red인경우
//Red 왼쪽으로 모으기
//순방향
if (balls2[i] == pivotr) {
if (balls2[i] == balls2[predRight]) {
predRight++;
}
else {
int tmp = balls2[predRight];
balls2[predRight] = balls2[i];
balls2[i] = tmp;
predRight++;
rrcnt++;
// cout << balls2 << endl;
}
}
//blue인경우
//blue 오른쪽으로 모으기
//역방향
if (balls3[n-1-i] == pivotb) {
if (balls3[n - 1 - i] == balls3[pblueleft]) {
pblueleft--;
}
else {
int tmp = balls3[pblueleft];
balls3[pblueleft] = balls3[n - 1 - i];
balls3[n - 1 - i] = tmp;
pblueleft--;
blcnt++;
//cout << balls3 <<endl;
}
}
//red인경우
//red 오른쪽으로 모으기
//역방향
if (balls4[n - 1 - i] == pivotr) {
if (balls4[n - 1 - i] == balls4[predleft]) {
predleft--;
}
else {
int tmp = balls4[predleft];
balls4[predleft] = balls4[n - 1 - i];
balls4[n - 1 - i] = tmp;
predleft--;
rlcnt++;
//cout << balls4 << endl;
}
}
}
gCnt.push_back(rrcnt);
gCnt.push_back(rlcnt);
gCnt.push_back(brcnt);
gCnt.push_back(blcnt);
sort(gCnt.begin(), gCnt.end());
cout << gCnt[0];
return 0;
}