[백준/JAVA] 20365번 블로그2 - 그리디 알고리즘

문제

내용

주어진 문제는 위와 같다.

이번 문제의 힌트는 이미 주어져 있다.

힌트는 다음과 같다.

즉, 칠하는 일이 귀찮으니 최소 작업 횟수를 구하는 방법이다.

풀이

일단 가장 많이 칠해야 하는 색깔을 붓는다고 생각하고, 적은 색깔을 일일이 칠해주는 경우가 최소 경우일 것이다.

구하는 방법은 다음과 같다.

입력 받을 때 중복을 제거한다.
ex) BB RRR B RR B => B R B R B 로 변환해서 저장한다.
이렇게 했을 때 가장 적은 색깔을 찾는다. 같아도 상관 없다.
색깔이 칠해질 값에 + 1을 한 값이 답이다.

코드

코드 설명

배열의 중복이 삭제되면 크기가 어느정도 일지 모른다. 따라서 ArrayList로 중복이 제거된 배열을 선언한다.
첫 시작값은 직접 세어주고 이후 값부터는 반복문을 통해 진행한다.
ArrayList인 arr의 가장 마지막 인덱스를 지정해주기 위해 arr.size() - 1을 사용한다.

제출 코드

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();
    }
}