문제 출처

1. 문제설명

  • 빨간색 볼과 파란색 볼이 일직선상에 섞여 놓여 있을 때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다.
  • 한번 어떤 색의 공을 옮기면, 같은 색의 공만 옮길 수 있다.
  • 같은 색끼리 모을 때 최소 이동횟수를 구하라.



2. 알고리즘 설계

  • 빨간공과 파란공 두 종류의 공이 있다.
  • 같은 색끼리 모으려면 어떤 방법이 있을까?
    • 어떤 색의 공을 왼쪽으로만 옮기는 방법
    • 오른쪽으로만 옮기는 방법
  • 좌/우를 병행하지 않는다.
    • 공이 두개고, 인접해야 하기 때문에 방향을 바꿀 필요가 없다.



3. 로직

  • 왼쪽으로 어떤 색의 공을 옮기는 방법
  • 오른쪽으로 어떤 색의 공을 옮기는 방법
  • 각각의 경우를 모두 구해 4가지 경우 중 최소값을 그리디하게 취하면 된다.
  • 알고리즘
    • 빨간 공을 만나면, red_temp를 1로 설정하고, 빨간 공의 카운팅은 blue_temp를 더한다.
    • 파란 공을 만나면, blue_temp를 1로 설정하고, 파란 공의 카운팅은 red_temp를 더한다.
  • 위와 같이 구현하면 각 방향에 대해 하나의 for-loop로 처리할 수 있다.



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, r_tmp = 0, r_cnt = 0, b_tmp = 0, b_cnt = 0, ans;
	string str;

	cin >> n >> str;

	for (int i = 0; i < str.size(); i++) {
		if (str[i] == 'R') {
			r_tmp = 1;
			r_cnt += b_tmp;
		}
		else {
			b_tmp = 1;
			b_cnt += r_tmp;
		}
	}

	ans = min(r_cnt, b_cnt);

	r_tmp = 0, r_cnt = 0, b_tmp = 0, b_cnt = 0;
	for (int i = str.size() - 1; i >= 0; i--) {
		if (str[i] == 'R') {
			r_tmp = 1;
			r_cnt += b_tmp;
		}
		else {
			b_tmp = 1;
			b_cnt += r_tmp;
		}
	}

	ans = min(ans, min(r_cnt, b_cnt));
	cout << ans;

	return 0;
}