[BOJ] 17615: 볼 모으기(Java)

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

17615번: 볼 모으기

 

문제

 

입력

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

 

출력

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

 

난이도

실버 1

 

Sol

① 공의 색깔을 선택한 후 왼쪽으로 옮길 때, 왼쪽에 위치한 공부터 순서대로 옮기는 경우가 가장 공을 적게 옮길 수 있는 경우다. 즉, 가장 처음으로 옮기는 공부터 쭉 개수를 세면 해당 공을 왼쪽으로 옮기는 경우의 수의 최솟값이 된다. 오른쪽도 마찬가지!

② 빨간 공을 움직여 왼쪽으로 모으는 경우, 빨간 공을 움직여 오른쪽으로 모으는 경우, 파란 공을 움직여 왼쪽으로 모으는 경우, 파란 공을 움직여 오른쪽으로 모으는 경우 → 네 가지 경우 공을 움직이는 횟수를 각각 구해서 최솟값을 찾는다

import java.io.*;
import java.lang.*;
import java.util.StringTokenizer;

/*
* 2023-07-25
* BOJ 17615: 볼 모으기
* 빨간 공을 움직여 왼쪽으로 모으는 경우 | 빨간 공을 움직여 오른쪽으로 모으는 경우
* 파란 공을 움직여 왼쪽으로 모으는 경우 | 파란 공을 움직여 오른쪽으로 모으는 경우
* 네 가지 경우 공을 움직이는 횟수를 각각 구해서 최솟값을 찾는다
* */

public class B17615_볼모으기 {
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine()); // 볼의 총 개수
        String input = bf.readLine();
        char[] arr = new char[N];

        for(int i=0; i<N; i++){
            char c = input.charAt(i);
            arr[i] = c;
        }
        // input

        boolean isBlue = false;
        int count = 0;
        for(char i : arr){
            if(i=='B') isBlue = true;
            if(isBlue && i == 'R') count++;
        }
        int min = count;
        // 빨간 공을 움직여 왼쪽으로 모으는 경우 : 처음으로 파란 공이 나온 이후부터 나오는 빨간 공들의 수를 센다

        isBlue = false;
        count = 0;
        for(int i=N-1; i>=0; i--){
            if(arr[i]=='B') isBlue = true;
            if(isBlue && arr[i] == 'R') count++;
        }
        min = Integer.min(min, count);
        // 빨간 공을 움직여 오른쪽으로 모으는 경우 : 배열의 맨 뒤부터 시작, 처음으로 파란 공이 나온 이후부터 나오는 빨간 공들의 수를 센다

        boolean isRed = false;
        count = 0;
        for(char i : arr){
            if(i=='R') isRed = true;
            if(isRed && i == 'B') count++;
        }
        min = Integer.min(min, count);
        // 파란 공을 움직여 왼쪽으로 모으는 경우 : 처음으로 빨간 공이 나온 이후부터 나오는 파란 공들의 수를 센다

        isRed = false;
        count = 0;
        for(int i = N-1; i>=0; i--){
            if(arr[i]=='R') isRed = true;
            if(isRed && arr[i] == 'B') count++;
        }
        min = Integer.min(min, count);
        // 파란 공을 움직여 오른쪽으로 모으는 경우 : 배열의 맨 뒤부터 시작, 처음으로 빨간 공이 나온 이후부터 나오는 파란 공들의 수를 센다
        // operation

        System.out.println(min);
        // output
    }
}

 

😏

시간을 줄이고 싶어서 반복문 네 개를 두 개씩 묶어서 루프를 두 번만 돌게 했는데(빨간 공과 파란 공을 왼쪽으로 모으는 경우 | 빨간 공과 파란 공을 오른쪽으로 모으는 경우) 실행 시간 상 드라마틱한 차이가 있지는 않았다 ..

아래쪽이 반복문 네 개, 위쪽이 반복문 두 개를 포함한 코드이다