3427 볼 모으기 (정올)

 

접근방식

처음에 이런 방식을 생각해 보았지만 예제 2에서 오류를 발견함.

아래 코드는 주어진 char 배열에서 R과 B의 세그먼트 (ex. RRR, BBB)같이 연속되어 있는 알파벳의 카운트만 계산해줌.

int countBall(int N, char balls[]){

    int rcount = 0, bcount = 0;

    char curcolor = balls[0];    

    if (curcolor == 'R'){
        rcount += 1;
    }else if (curcolor == 'B'){
        bcount += 1;
    }

    for (int i = 1; i < N; i++){
        if (balls[i] != curcolor){
            curcolor = balls[i];
            if (curcolor == 'R'){
                rcount += 1;
            }else{
                bcount += 1;
            }
        }

    }

    return min(rcount, bcount);
}

 

이걸로는 구할 수가 없고, 먼저 R과 B의 occurence를 세준 다음

B나 R을 왼쪽으로 모는 경우와 오른쪽으로 모는 경우를 따로 나누고, 

같은 알파벳이 연속해서 나오면 카운터를 늘려줘서 만약 첫 알파벳이 R이면 R에서 카운터를 빼주고 B면 B에서 카운터를 빼준다.

그걸 0에서 N 그리고 N-1부터 0 까지 반복해서 오른쪽 왼쪽의 경우를 따로 나누고, 최종적으로 최솟값을 포함한 ans 를 출력시켜준다. 

 

코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int countBall(int N, string balls){
    int rc = count(balls.begin(), balls.end(), 'R');
    int bc = count(balls.begin(), balls.end(), 'B');

    int ans = min(rc, bc);

    int cnt = 0; 

    for (int i = 0; i < N; i ++){
        if (balls[i] != balls[0]) break;
        cnt++;
    }
    if (balls[0] == 'R'){
        ans = min(ans, rc - cnt);
    }else{
        ans = min(ans, bc - cnt);
    }

    int revc = 0; 

    for (int i = N - 1; i >= 0; i--){
        if (balls[i] != balls[N - 1]) break;
        revc++;
    }
    if (balls[N - 1] == 'R'){
        ans = min(ans, rc - revc);
    }else{
        ans = min(ans, bc - revc);
    }

    return ans;

}

int main(){
    
    int n;
    cin >> n;
    string b;
    
    cin >> b;

    cout << countBall(n, b);


}