[BOJ] 백준 17615 볼 모으기

출처: https://www.acmicpc.net/problem/17615

 Input 

9

RBBBRBRRR

 

 Output 

2

 

① 각 색깔의 개수를 센다. (빨간색 볼, 파란색 볼의 개수)

    → 더 적은 개수의 색깔을 지닌 공을 옮기는 것이 효율적입니다.

② 왼쪽부터 연속된 색깔의 개수를 세어서 그만큼 해당색의 전체개수에서 뺀다.

    → 기존의 답보다 작으면 갱신 (나머지 볼을 왼쪽으로 옮기는 경우)

③ 오른쪽부터 연속된 색깔의 개수를 세어서 그만큼 해당색의 전체개수에서 뺀다.

    → 기존의 답보다 작으면 갱신 (나머지 볼을 오른쪽으로 옮기는 경우)

 

R B B B R B R R R

① 빨간색볼이 5 개, 파란색볼이 4 개로 정답 후보는 4 이다.

② 왼쪽부터 연속한 볼은 빨간색 1 개이다. 

    → 빨간색볼이 총 5 개이므로 왼쪽에 연속한 1 개를 제외해서 5 – 1 = 4 이다.

③ 오른쪽부터 연속한 볼은 빨간색 3개이다. 

    → 빨간색볼이 총 5개이므로 오른쪽에 연속한 3개를 제외하면 5 – 3 = 2 이다.

따라서 제일 작은 값인 2 가 정답이다.

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
using namespace std;
inline int min(int A, int B) { return A < B ? A : B; }
char ball[500005];
int N, ans, redBallCnt, blueBallCnt;

int main(){
    int i, cnt = 0;
    scanf("%d %s", &N, ball);
    
    // 1) 각 색깔의 개수를 센다.
    //    작은 값이 답 후보이다. (그 색의 모든 볼을 다 옮기는 경우)
    for (i = 0; i < N; i++) {
        if (ball[i] == 'R') redBallCnt++;
        else blueBallCnt++;
    }
    ans = min(redBallCnt, blueBallCnt);

    // 2) 가장 왼쪽부터 연속된 색깔의 개수를 세어서 해당색의 전체개수에서 뺀다.
    //    기존의 답보다 작으면 갱신한다. (나머지 볼을 왼쪽으로 옮기는 경우)
    for (i = 0; i < N; i++) {
        if (ball[i] != ball[0]) break;
        cnt++;
    }
    if (ball[0] == 'R') ans = min(ans, redBallCnt - cnt);
    else ans = min(ans, blueBallCnt - cnt);

    // 3) 가장 오른쪽부터 연속된 색깔의 개수를 세어서 해당색의 전체개수에서 뺀다.
    //    기존의 답보다 작으면 갱신한다. (나머지 볼을 오른쪽으로 옮기는 경우)
    cnt = 0;
    for (i = N - 1; i >= 0; i--) {
        if (ball[i] != ball[N - 1]) break;
        cnt++;
    }

    if (ball[N - 1] == 'R') ans = min(ans, redBallCnt - cnt);
    else ans = min(ans, blueBallCnt - cnt);

    printf("%d\n", ans);
}