[백준] 17615 볼 모으기 - 구현 + 그리디 JAVA

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

17615번: 볼 모으기

코드설명

구현과 그리디를 활용하는 문제입니다.

 

문제의 로직은,

위의 볼의 이동수를 구할때 한쪽으로 모으는 경우에는 한쪽의 처음에 모여있는 firstBallCnt를 구한뒤

firstBallCnt - blueCnt를 빼면 모여있는 한쪽 볼 이외의 공의 개수가 나오는데 그 공의 개수가 이동횟수입니다.

 

그리고 위의 로직을 이용하여

 

1. 'R'을 맨 왼쪽으로 모으는 경우 RRRRRBBBBB

2. 'R'을 맨 오른쪽으로 모으는 경우 BBBBBRRRR

3. 'B'을 맨 왼쪽으로 모으는 경우 BBBBBRRRRR

4. 'B'을 맨 오른쪽으로 모으는 경우 RRRRBBBBB

 

위의 4가지를 모두 구하여서 최소값을 출력합니다.

 

코드

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


public class Main {
	public static int N, K;
	public static char[] arr;
	public static int answer = 500001;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	
    	arr = new char[N];
    	st = new StringTokenizer(br.readLine());
		arr = st.nextToken().toCharArray();
		
		int firstBallCnt = 0;
		int redCnt = 0;
		int blueCnt = 0;		
	
		//전체 공의 색깔 계산
		for(int i=0;i<N;i++) {
			if(arr[i] == 'R') {
				redCnt += 1;
			}
			if(arr[i] == 'B'){
				blueCnt += 1;
			}
		}
			
		//1. 'R'을 맨 왼쪽으로 모으는 경우 RRRRRBBBBB
		for(int i=0;i<N;i++) {
			if(arr[i] == 'R') {
				firstBallCnt += 1;
			}else {
				break;
			}
		}
		
		answer = Math.min(answer,  redCnt - firstBallCnt);
		
		firstBallCnt = 0;
		//2. 'R'을 맨 오른쪽으로 모으는 경우
		for(int i=N-1;i>=0;i--) {
			if(arr[i] == 'R') {
				firstBallCnt += 1;
			}else {
				break;
			}
		}
		
		answer = Math.min(answer,  redCnt - firstBallCnt);
		
		firstBallCnt = 0;
		//1. 'R'을 맨 왼쪽으로 모으는 경우 RRRRRBBBBB
		for(int i=0;i<N;i++) {
			if(arr[i] == 'B') {
				firstBallCnt += 1;
			}else {
				break;
			}
		}
		
		answer = Math.min(answer,  blueCnt - firstBallCnt);
		
		firstBallCnt = 0;
		//2. 'R'을 맨 오른쪽으로 모으는 경우
		for(int i=N-1;i>=0;i--) {
			if(arr[i] == 'B') {
				firstBallCnt += 1;
			}else {
				break;
			}
		}
		
		answer = Math.min(answer,  blueCnt - firstBallCnt);		
		
		System.out.println(answer);
    }
    
      
}