알고리즘 공부

백준 볼 모으기

컴퓨터과학 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;
}