백준 17615번 볼 모으기 (C++)

문제 링크 : https://www.acmicpc.net/problem/17615

17615번: 볼 모으기

문제 요약

 

1.  N개의 공이 일렬로 주어집니다. 각 공의 색은 'R' 또는 'B'입니다.

2. 한 번에 한 개의 공을 선택하여 원하는 위치에 삽입할 수 있습니다.

단,  첫 번째로 선택한 공의 색과 동일한 색의 공만 선택하여 이동할 수 있습니다.

3. 최소 이동횟수로 'R'과 'B'공을 같은색끼리 모을 수 있도록 하세요.

 

핵심 포인트

 

N의 값이 최대 500,000이 주어지므로, 무턱대로 2중 for문을 사용했다가 시간초과가 발생할 수 있습니다.

DP, 이분탐색, 온갖 방법을 선택해도 시간초과가 예상되니, Greedy 유형답게 원초적이고 최대한 단순한 공식을 생각하는 것이 좋습니다.

 

예를들어 다음과 같이 공이 놓여져있다고 가정합시다.

문제를 풀기 위해 다음 4가지를 구해봅시다.

 

1. 빨간색 공을 왼쪽으로 몰아넣는 경우
2. 빨간색 공을 오른쪽으로 몰아넣는 경우
3. 파란색 공을 왼쪽으로 몰아넣는 경우
4. 파란색 공을 오른쪽으로 몰아넣는 경우

1번 '빨간색 공을 왼쪽으로 몰아넣기'의 경우 다음과 같은 로직으로 오로지 for문 한번으로 정답을 구할 수 있습니다.

문자열 s = R B B R B R
바꿔야할 공의 갯수 cnt = 0
목표 = 빨간 공을 왼쪽으로 몰아넣는 경우

s[0]은 R이니 cnt는 0입니다. 아직 B를 못만났기 때문입니다.
s[1]은 B이니 cnt = 0입니다. B를 만났고, 이제 바꿔야할 R을 찾아야 합니다.
s[2]은 B이니 cnt = 0입니다. ""
s[3]은 R이니 cnt = 1입니다. 위치를 바꿔야할 R을 찾았습니다.
s[4]는 B이니 cnt = 1입니다. B의 위치는 바꿀 필요가 없습니다.
s[5]는 R이니 cnt = 2입니다. 위치를 바꿔야할 R을 찾았습니다.
cnt = 2

위와 같은 방식으로 앞서 언급된 4가지를 모두 구하면, 정답은 파란공을 왼쪽으로 몰아넣어 '1'이 됩니다.

 

문제 풀이

 

1. n과 s의 값을 입력받고 R과 B를 각각 그룹핑하는 작업을 시작합니다.

    cin >> n;
    cin >> s;
    group('R');
    group('B');

 

2. 다음은 그룹핑하는 함수의 내부입니다.

void group(char x){
    cnt = 0;
    bool ch = false;
    for(int i=0; i<s.size(); i++){ // left
        if(s[i]!=x) ch = true;
        else if(ch&&s[i]==x) cnt++;
    }
    if(ans>cnt) ans = cnt;
    ch = false;
    cnt = 0;
    for(int i=s.size()-1; i>=0; i--){ // right
        if(s[i]!=x) ch = true;
        else if(ch&&s[i]==x) cnt++;
    }
    if(ans>cnt) ans = cnt;
}

여기서 left의 예시만 이해하면 됩니다.

    cnt = 0; // 1
    bool ch = false; 
    for(int i=0; i<s.size(); i++){ // 2
        if(s[i]!=x) ch = true; // 3
        else if(ch&&s[i]==x) cnt++; // 4
    }
    if(ans>cnt) ans = cnt; // 5

(1) 바꿔야할 공의 갯수는 0으로 초기화하고 ch(목표 공을 찾기위한 분기점)는 false로 초기화합니다.

(2) 왼쪽에 공을 몰아넣을 경우, 0부터 시작합니다. 반대로 오른쪽으로 공을 몰아넣는 경우 s.size()-1부터 시작합니다.

(3) 만약 s[i]가 목표 공이 아닐 경우, ch는 true로 바꿔줍니다. 이 분기점을 기준으로 s[i]가 위치를 바꿔야할 색상의 공인지 아닌지를 세어주면됩니다.

(4) ch가 true이고 s[i]가 위치를 바꿀 색상의 공일 경우, cnt를 +1해줍니다.

(5) ans는 최초에 MAX값으로 초기화되어있습니다. ans보다 cnt가 작을 경우, ans를 cnt로 값을 저장합니다.

 

3. 이렇게 빨간공을 왼쪽 / 오른쪽으로 몰아넣기, 파란공을 왼쪽 / 오른쪽으로 몰아넣기 과정을 통해 구해진 ans를 출력합니다.

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

int n,cnt,ans=987654321;
string s;

void group(char x){
    cnt = 0;
    bool ch = false;
    for(int i=0; i<s.size(); i++){ // left
        if(s[i]!=x) ch = true;
        else if(ch&&s[i]==x) cnt++;
    }
    if(ans>cnt) ans = cnt;
    ch = false;
    cnt = 0;
    for(int i=s.size()-1; i>=0; i--){ // right
        if(s[i]!=x) ch = true;
        else if(ch&&s[i]==x) cnt++;
    }
    if(ans>cnt) ans = cnt;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    cin >> s;
    group('R');
    group('B');
    cout << ans << "\n";
    return 0;
}