⚒️ Coding Test

[백준] 볼 모으기 - 자바(Java)

dev-ong 2024. 7. 18. 11:43

문제 링크

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

문제 설명

빨간색 볼과 파란색 볼이 <그림 1>에서 보인 것처럼 일직선상에 섞여 놓여 있을 때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 볼을 옮기는 규칙은 다음과 같다.

  1. 바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.
  2. 옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.

예를 들어, 처음에 볼이 <그림 1>에서 보인 것처럼 있을 때, 빨간 볼을 <그림 2>에서 보인 것처럼 옮긴 후, <그림 3>에서 보인 것처럼 옮긴다면 두 번 만에 같은 색끼리 모을 수 있다.

반면에 파란색 볼을 선택하여 에서 보인 것처럼 옮기면(화살표에 있는 수는 옮기는 순서를 나타낸다) 네 번을 옮겨야 같은 색의 볼끼리 모을 수 있다.

일직선상에 놓여 있는 볼에 관한 정보가 주어질 때, 규칙에 따라 볼을 이동하여 같은 색끼리 모으되 최소 이동횟수를 찾는 프로그램을 작성하시오.

입력

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

출력

최소 이동횟수를 출력한다.

입출력 예

입력 출력
9
RBBBRBRRR		 2
8
BBRBBBBR		 1

 

문제 풀이

[고려사항]

볼의 총 개수인 N은 최대 500,000(50만)이고, 시간 제한은 1초(추가 시간 없음)이므로, O(N^2)이 나오지 않게 고려하여서 구현해야한다.

[알고리즘, 구현방법]

이 문제는 *그리디 알고리즘과 구현으로 해결해야한다.

*그리디 알고리즘(Greedy Algorithm): 최적해를 구하는 알고리즘으로, 각 단계에서 최적이라고 생각되는 것을 선택해나가는 방식으로 진행하여 최종적인 해답을 찾는 알고리즘이다.

 

빨간공(R), 파란공(B)을 각각 왼쪽, 오른쪽으로 모으는 경우에 대해 모두 확인해야한다. (총 4번) 

옮기는 횟수는 옮기려는 방향의 가장 끝 인덱스부터, 현재 확인하려하는 볼의 연속된 개수를 해당 색상의 총 볼의 개수에서 빼주면 된다. 

  • 빨간 공(R)을 왼쪽/오른쪽으로 옮기는 횟수: 빨간 공의 총 개수 - 왼쪽/오른쪽에 연속으로 있는 빨간 공의 개수
  • 파란 공(B)을 왼쪽/오른쪽으로 옮기는 횟수: 파란 공의 총 개수 - 왼쪽/오른쪽에 연속으로 있는 파란 공의 개수

문제의 예시로 예를 들어보면,

빨간 공(R)을 왼쪽으로 옮기는 경우, 가장 왼쪽에 있는 빨간 공(R) 하나를 제외한 4개의 공을 옮겨야하고, 옮기는 횟수는 4회이다.

파란 공(B)을 왼쪽으로 옮기는 경우, 가장 왼쪽에 있는 파란 공이 없으므로 총 4개의 파란 공을 옮겨야하고, 횟수는 4회이다.

오른쪽 방향에서는 오른쪽 끝에 있는 각 공의 수를 확인해서 계산하면 된다.

[풀이 과정]

1. 입력을 받아서 각 공의 총 개수를 저장 | 공의 위치를 배열로 저장

2. 한 종류의 공만 있는 경우, 답은 0

3. 왼쪽 끝으로 빨간 공과 파란 공을 옮기는 경우를 계산

  • 왼쪽 끝부터 빨간 공, 파란 공이 연속적으로 있을때까지만 공의 개수(cnt) 카운팅
  • 옮기는 횟수(moved) 계산 (moved = total - cnt)하고 횟수 최솟값 갱신

4. 오른쪽 끝으로 빨간 공과 파란 공을 옮기는 경우를 계산

  • 왼쪽 끝으로 모은 경우와 방향만 다름

5. 횟수 최솟값(min) 출력

 

정답 코드

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

    int N = Integer.parseInt(br.readLine());
    String ball = br.readLine();

    char[] balls = new char[N];
    int[] total = {0, 0}; // 빨간 공의 수, 파란 공의 수
    for(int i=0; i<N; i++) {
        char c = ball.charAt(i);
        balls[i] = c;
        // 색상별 공의 개수 카운팅
        if (c == 'R') total[0]++;
        else total[1]++;
    }
    // 한 종류의 공만 있는 경우
    if (total[0] == N || total[1] == N) {
        System.out.println(0);
        return;
    }

    int min = N+1;
    char[] color = {'R', 'B'};
    // 왼쪽 끝으로 모으는 경우
    for (int b = 0; b < 2; b++) {
        int idx = 0;
        int cnt = 0;
        // 공 순서에서 옮기는 공이 연속으로 존재할때까지만 왼쪽 끝에 있는 공의 수 카운팅
        while (balls[idx++] == color[b]) {
            cnt++;
        }
        int moved = total[b] - cnt; // 옮긴 횟수 계산 (총 공의 개수 - 왼쪽 끝에 있는 공의 수)
        if (moved < min) min = moved; // 최솟값 갱신
    }
    // 오른쪽 끝으로 모으는 경우
    for (int b = 0; b < 2; b++) {
        int idx = N - 1;
        int cnt = 0;
        // 공 순서에서 옮기는 공이 연속으로 존재할때까지만 오른쪽 끝에 있는 공의 수 카운팅
        while(balls[idx--] == color[b]) {
            cnt++;
        }
        int moved = total[b] - cnt; // 옮긴 횟수 계산 (총 공의 개수 - 왼쪽 끝에 있는 공의 수)
        if (moved < min) min = moved; // 최솟값 갱신
    }

    System.out.println(min);
}