[BOJ_17615] 볼 모으기

설명

---

왼쪽으로 모으는 경우 오른쪽으로 모두 모으는 경우를 카운트 한다. 이것이 가능한 이유는 카운트 해야 할 예시가 R,B 2가지로 2가지를 서로 다른 위치로 배정해서 모두 같은 곳으로 옮기면 되므로 한 쪽으로 몰아준다는 아이디어로 구현을 하면된다.

 

예시로, RBBBRRB의 경우 R을 오른쪽으로 모두 옮긴 경우 BBB B RRR 와 R을 왼쪽으로 모두 옮기는 경우인 R RR BBB B 가 존재한다. 이것을 B의 경우에도 적용하여 최저로 옮긴 경우를 반환하면 된다.

 

이것을 구현하기 쉽게 이해하기 위해서는 최초의 가장자리 위치의 값들만 제외하고 떨어진 것들만 옮기면 된다는 생각을 가지고 코드를 구현하면 바로 구현 가능하다.

 

코드

---

package Greedy;
import java.io.*;
import java.util.*;

public class BOJ_17615 {
    static int N;
    static int ans;
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        N = Integer.parseInt(tk.nextToken());
        ans = Integer.MAX_VALUE;
        String str = in.readLine();
        int cnt = 0;
        for(int i = 0; i < N; i++){
            if(str.charAt(i) == 'R'){
                cnt++;
            }
        }
        ans = Math.min(ans,(N-cnt) - go(0,new StringBuilder(str).reverse().toString(),'B'));
        ans = Math.min(ans,cnt - go(0,str,'R'));
        ans = Math.min(ans,(N-cnt) - go(0,str,'B'));
        ans = Math.min(ans,cnt - go(0,new StringBuilder(str).reverse().toString(),'R'));

        System.out.println(ans);
    }

    private static int go(int cnt, String str, char start) {
        for(int i = 0; i < N; i++){
            if(str.charAt(i) == start){
                cnt++;
            }else{
                break;
            }
        }
        return cnt;
    }
}

 

17615번: 볼 모으기