[백준_17615] 볼 모으기

[문제]

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

 

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

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

 

<그림 1>

<그림 2>

<그림 3>

 

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

 

<그림 4>

 

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_17615 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		String str=sc.next();
		int result=Integer.MAX_VALUE;
		
		int red=0,blue=0;
		for(int i=0;i<n;i++) {
			if(str.charAt(i)=='R')
				red++;
			else
				blue++;
		}
		
		/*
		 * 빨간공 모두 왼쪽으로 옮기는 경우
		 * 기존에 제일 왼쪽에 있는 빨간공은 옮기지 않아도 되기 때문에 
		 * 모든 빨간공의 개수 - 왼쪽에 있는 빨간공의 개수를 하면 옮겨야 하는 빨간공의 개수가 나온다
		 * 오른쪽으로 옮기는 경우는 반대로 코드 짜면 됨
		 */
		int red_left=0;
		for(int i=0;i<n;i++) {
			if(str.charAt(i)=='R')
				red_left++;
			else
				break;
		}
		result=Math.min(red-red_left,result);
		
		// 빨간공 모두 오른쪽으로 옮기는 경우
		int red_right=0;
		for(int i=n-1;i>=0;i--) {
			if(str.charAt(i)=='R')
				red_right++;
			else
				break;
		}
		result=Math.min(red-red_right, result);
		
		// 파란공 모두 왼쪽으로 옮기는 경우
		int blue_left=0;
		for(int i=0;i<n;i++) {
			if(str.charAt(i)=='B')
				blue_left++;
			else
				break;
		}
		result=Math.min(blue-blue_left,result);
				
		// 파란공 모두 오른쪽으로 옮기는 경우
		int blue_right=0;
		for(int i=n-1;i>=0;i--) {
			if(str.charAt(i)=='B')
				blue_right++;
			else
				break;
		}
		result=Math.min(blue-blue_right, result);
		
		System.out.println(result);
	}
}

 

[고찰]

 이번 문제는 그리디 문제로 해결 방법만 알아내면 코드는 쉽게 구현할 수 있었다. 해당 문제는 가능한 경우의 수가 빨간공을 모두 왼쪽, 오른쪽으로 옮기는 경우와 파란공을 모두 왼쪽, 오른쪽으로 옮기는 경우 총 4가지가 나올수 있다. 이 4가지의 경우를 모두 탐색하여 이동횟수가 가장 작은 것을 출력하면 된다. 

 공을 옮기는 방법은 생각보다 쉬웠는데, 예를 들어 빨간공을 모두 왼쪽으로 옮기는 경우는 모든 빨간공의 개수에서 이미 왼쪽에 있는 빨간공의 개수를 빼는 방식으로 해결할 수 있다.