[백준] 17615 볼 모으기 - Greedy / Java

• 문제 링크

17615번: 볼 모으기

 

• 풀이 과정

입력에서 R, B 의 개수를 세어 둘 중 작은 값을 구해 최소값을 초기화한다.

가장 왼쪽과 오른쪽의 연속된 색의 개수를 각각 해당 색의 전체 개수에서 뺀 값을 구한다.

이를 최소값과 비교하여 갱신해 최소 이동 횟수를 도출한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        String input = br.readLine();

        int red = 0, blue = 0;
        for (int i = 0; i < n; i++) {
            if (input.charAt(i) == 'R')
                red++;
            else
                blue++;
        }
        int min = Math.min(red, blue);

        char first = input.charAt(0);
        char last = input.charAt(n - 1);

        int cnt = 1;
        while (cnt < n && input.charAt(cnt) == first)
            cnt++;

        min = first == 'R' ? Math.min(min, red - cnt) : Math.min(min, blue - cnt);

        cnt = 1;
        while (cnt < n && input.charAt(n - 1 - cnt) == last)
            cnt++;

        min = last == 'R' ? Math.min(min, red - cnt) : Math.min(min, blue - cnt);

        bw.write(String.valueOf(min));
        bw.flush();
    }

}