17615 : 볼 모으기

☀️ 문제 링크

• https://www.acmicpc.net/problem/17615

🌻 문제 간단한 설명

• 그리디 알고리즘을 통해 해결할 수 있다.
• 색깔별로 양쪽으로 나눌경우 이동거리의 최소값을 구하는 문제이다.
  
  • RBBBRBRRR : 저걸 오른쪽으로 옮긴다.
  • RBBBBRRRR(이동횟수 1) : 저걸 오른쪽으로 옮긴다.
  • BBBBRRRRR(이동횟수 2) 끝
    • 다른방법도있음
  • RBBBRBRRRR(이동횟수 1) : 4번자리로 이동
  • BBBRRBRRRR(이동횟수 2) : 3번자리로 이동 끝

⚡️ 풀이

🌝 전체 코드

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

public class Main {

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

        int N = Integer.parseInt(br.readLine());
        char[] balls = br.readLine().toCharArray();

        int redBall = 0;
        int blueBall = 0;

        for (char ball : balls) {
            if (ball == 'R') {
                redBall++;
            } else {
                blueBall++;
            }
        }

        int searchFrontRed = redBall - searchFront(balls, 'R');
        int searchFrontBlue = blueBall - searchFront(balls, 'B');
        int searchBackRed = redBall - searchBack(balls, 'R');
        int searchBackBlue = blueBall - searchBack(balls, 'B');

        System.out.println(Math.min(searchFrontRed, Math.min(searchFrontBlue, Math.min(searchBackRed, searchBackBlue))));
    }

    private static int searchFront(char[] balls, char color) {
        int count = 0;
        for (char ball : balls) {
            if (ball == color) {
                count++;
            } else {
                break;
            }
        }

        return count;
    }

    private static int searchBack(char[] balls, char color) {
        int count = 0;
        for (int i = balls.length - 1; i >= 0; i--) {
            if (balls[i] == color) {
                count++;
            } else {
                break;
            }
        }

        return count;
    }
}

🌛 코드별 설명

앞에서 부터 탐색

• 만약 왼쪽으로 R을 몰아버릴 경우 (RBBBRBRRR -> RRRRRBBBB)
  • 전체 R볼의 개수(5) - 왼쪽에서 연속된 R볼의 갯수(1)이다.
  • RBBBRBRRR -> RRBBBBRRR (Count 1)
  • RRBBBBRRR -> RRRBBBBRR (Count 2)
  • RRRBBBBRR -> RRRRBBBBR (Count 3)
  • RRRRBBBBR -> RRRRRBBBB (Count 4)

int searchFrontRed = redBall - searchFront(balls, 'R');

private static int searchFront(char[] balls, char color) {
    int count = 0;
    for (char ball : balls) {
        if (ball == color) {
            count++;
        } else {
            break;
        }
    }

    return count;
}

뒤에서 부터 탐색

• 만약 오른쪽으로 R을 몰아버릴 경우(RBBBRBRRR -> BBBBRRRRR)
  • 전체 R볼의 개수(5) - 오른쪽에서 연속된 R볼의 갯수(3)이다.
  • RBBBRBRRR -> RBBBBRRRR (Count 1)
  • RBBBBRRRR -> BBBBRRRRR (Count 2)

int searchBackRed = redBall - searchBack(balls, 'R');

private static int searchBack(char[] balls, char color) {
    int count = 0;
    for (int i = balls.length - 1; i >= 0; i--) {
        if (balls[i] == color) {
            count++;
        } else {
            break;
        }
    }

    return count;
}

🌞 끝으로

그리디 알고리즘 문제를 풀어봤다.
그리디 알고리즘은 주어진 상황에서 최적해를 구하는 알고리즘이지 전체적으로 봤을때 최적해를 보장하지 않는 알고리즘이다.
그래서 앞에 R, 앞에 B, 뒤에 R, 뒤에 B 이렇게 주어진 조건에 한에서 최적해를 구하고 그 중에서 Math.min을 통해서 최적해를 찾았다.