알고리즘/백준

17615번 : 볼 모으기

코딍코딍 2022. 10. 2. 15:46

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

 

17615번: 볼 모으기

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

www.acmicpc.net

 

 

문제

 

 

코드

import java.io.*;

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());
        String str = br.readLine();

        int blueN=0; //맨 왼쪽 또는 맨 오른쪽에 뭉쳐있지 않은 파란공의 개수
        int redN=0; //맨 왼쪽 또는 맨 오른쪽에 뭉쳐있지 않은 빨간공의 개수
        int acum=0; //누적값

        //오른쪽으로 모으기
        if(str.charAt(0) =='B') blueN=1;
        else redN=1;
        for(int i=1;i<n;i++) {
            if(str.charAt(i) =='B') {
                if(str.charAt(i-1) == 'B') acum++; //연속된 B
                else { //끊긴경우
                    redN+=acum;
                    acum=1;
                }
            }else {
                if(str.charAt(i-1) == 'R') acum++; //연속된 R
                else { //끊긴경우
                    blueN+=acum;
                    acum=1;
                }
            }
        }
        int n1; //오른쪽으로 모았을 때 최소횟수
        if(blueN<=redN) n1=blueN;
        else n1=redN;

        //왼쪽으로 모으기
        blueN = redN = acum = 0;
        if(str.charAt(n-1) =='B') blueN=1;
        else redN=1;
        for(int i=n-2;i>=0;i--) {
            if(str.charAt(i) =='B') {
                if(str.charAt(i+1) == 'B') acum++; //연속된 B
                else { //끊긴경우
                    redN+=acum;
                    acum=1;
                }
            }else {
                if(str.charAt(i+1) == 'R') acum++; //연속된 R
                else { //끊긴경우
                    blueN+=acum;
                    acum=1;
                }
            }
        }
        int n2; //왼쪽으로 모았을 때 최소횟수
        if(blueN<=redN) n2=blueN;
        else n2=redN;

        if(n1>n2) System.out.println(n2);
        else System.out.println(n1);
    }
}

 

 

해결방법

입력받은 공들 중 맨 왼쪽 또는 맨 오른쪽에 뭉쳐있지 않은 파란 공과 빨간 공 개수 중 작은 값이 최소 이동 횟수이다.

오른쪽으로만 공을 이동 가능한 것으로 문제를 잘못 이해하여 2번째 시도만에 해결하였다.