[BOJ/JAVA] 17615번: 볼 모으기

17615번: 볼 모으기

[17615번: 볼 모으기

첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주

www.acmicpc.net](https://www.acmicpc.net/problem/17615)

키워드

바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다.

옮길 수 있는 볼의 색깔은 한 가지이다.

---

구현

최종적인 형태는 한쪽에는 R만 있고, 한쪽에는 B만 있는 형태가 될 것이다.

옮기는 횟수

가장 좌측의 연속된 색깔의 볼이 R인 경우를 생각해보자

가장 좌측부터 색깔이 달라지기 시작했을 때 B의 갯수와 R의 갯수를 카운트한다.

R : 4

B : 4

이 때 카운트 되는 값은 **해당 색깔을 가장 왼쪽으로 옮겼을 때 이동하는 횟수**를 나타낸다.

다시 가장 우측의 연속된 색깔의 볼이 R인 경우 (위 그림과 동일)

가장 우측부터 색깔이 달라지기 시작했을 때 B의 갯수와 R의 갯수를 카운트한다.

R : 2

B : 4

이 때 카운트 되는 값은 **해당 색깔을 가장 오른쪽으로 옮겼을 때 이동하는 횟수**를 나타낸다.

이때 카운트되는 값이 가장 값을 선택한다.

---

코드

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

public class java_17615 {
    static int N;
    static char ballList[];

    static class Pair {
        int startIndex, endIndex;

        public Pair(int startIndex, int endIndex) {
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }

        @Override
        public String toString() {
            return "Pair [startIndex=" + startIndex + ", endIndex=" + endIndex + "]";
        }

    }

    static Pair findStartEndIndex() {
        int startIndex = 0;
        char startColor = ballList[startIndex];

        for (; startIndex < ballList.length; startIndex++) {
            if (ballList[startIndex] != startColor) {
                break;
            }
        }

        int endIndex = ballList.length - 1;
        char endColor = ballList[endIndex];

        for (; endIndex >= 0; endIndex--) {
            if (ballList[endIndex] != endColor) {
                break;
            }
        }

        return new Pair(startIndex, endIndex);

    }

    static int countRB(Pair indexPair) {
        int result = Integer.MAX_VALUE;

        int redCount = 0;
        int blueCount = 0;

        // start 인덱스 부터 R의 갯수, B의 갯수를 카운트
        for (int i = indexPair.startIndex; i < ballList.length; i++) {
            if (ballList[i] == 'R') {
                redCount++;
            } else {
                blueCount++;
            }
        }

        result = Math.min(redCount, blueCount);

        redCount = 0;
        blueCount = 0;

        // end 인덱스 까지 R의 갯수, B의 갯수를 카운트
        for (int i = indexPair.endIndex; i >= 0; i--) {
            if (ballList[i] == 'R') {
                redCount++;
            } else {
                blueCount++;
            }
        }

        result = Math.min(result, Math.min(redCount, blueCount));

        return result;
    }

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

        // 같은 색 볼 끼리 인접하게 놓이도록 하려 한다.

        // 규칙 1. 바로 옆에 달느 색깔의 볼이 있다면 전부 뛰어 넘을 수 있음

        // 규칙 2. 옮길 수 있는 볼의 색깔은 한 가지 이다. (처음 선택하는 색깔의 볼만 옮길 수 있다.)

        // 왼쪽 끝, 오른쪽 끝 연속된 볼 이후의 볼 부터 시작해보자

        //
        N = Integer.parseInt(br.readLine());

        String ballString = br.readLine();
        ballList = ballString.toCharArray();

        Pair indexPair = findStartEndIndex();

        // System.out.println(indexPair);

        // startIndex가 length 라면...
        if (indexPair.startIndex == ballString.length() || indexPair.endIndex == -1) {
            System.out.println(0);
        } else {
            // firstIndex 부터 R의 수, B의 수를 찾는다.

            // endIndex 까지 R의 수, B의 수를 찾는다.
            int result = countRB(indexPair);

            System.out.println(result);
        }

        br.close();
    }
}

---