백준 20365번: 블로그2, 색이 이어지는 구간 세기

연속된 같은 색은 한 묶음입니다

백준 20365번 블로그2는 주어진 색 배열을 만드는 최소 색칠 횟수를 구하는 문제입니다.

백준 블로그2의 색칠 작업 조건과 문제 설명

문제에 주어진 힌트에서 풀이 방향을 잡았습니다.

한 색을 먼저 칠한 뒤 다른 색을 덧칠하는 블로그2 힌트

전체를 한 색으로 먼저 칠하고 다른 색이 필요한 구간만 덧칠하면 됩니다. 이때는 색의 칸 수보다 연속된 구간의 수를 봅니다.

중복을 줄인 뒤 두 색의 구간 수를 셉니다

예를 들어 BB RRR B RR B에서 연속 중복을 제거하면 B R B R B가 됩니다. B 구간은 세 개, R 구간은 두 개입니다. 전체를 B로 한 번 칠하고 R 구간 두 곳을 덧칠하면 모두 세 번 칠하게 됩니다.

그래서 두 색의 구간 수 중 작은 값에 전체를 칠하는 한 번을 더합니다. 두 구간 수가 같으면 어느 색을 먼저 칠해도 같습니다.

코드에서는 중복을 제거한 뒤의 길이가 정해져 있지 않아 ArrayList에 색을 저장했습니다. 첫 색을 넣고 한 번 센 뒤, 다음 색부터는 마지막에 저장한 색과 비교해서 색이 달라질 때만 리스트에 넣고 해당 색의 구간 수를 늘립니다. 마지막 원소의 위치는 arr.size() - 1입니다.

제출 코드

Java

import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        ArrayList<Character> arr = new ArrayList<>();

        //0 = B, 1 = R
        int[] cnt = new int[2];
        int N = Integer.parseInt(br.readLine());

        String line = br.readLine();
        arr.add(line.charAt(0));
        if(arr.get(0) == 'B') cnt[0]++;
        else if (arr.get(0) == 'R') cnt[1]++;

        for (int i = 1; i < N; i++) {
            if (!arr.get(arr.size() - 1).equals(line.charAt(i))) {
                char c = line.charAt(i);
                arr.add(c);
                if(c == 'B') cnt[0]++;
                else if (c == 'R') cnt[1]++;
            }
        }
        bw.write(String.valueOf(Math.min(cnt[0], cnt[1]) + 1));
        bw.flush();
    }
}