[자바] 백준 20365 - 블로그2 (java)

목차

문제 : boj20365

 

 

필요 알고리즘

• 그리디 알고리즘
  
  • 탐욕법으로 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  내가 생각한 방식은 다음 두 가지 경우 중 횟수가 작은쪽을 선택하는 것이다.

1. 전체를 파란색으로 칠한 후, 연속된 'R'들을 빨간색으로 칠한다.

2. 전체를 빨간색으로 칠한 후, 연속된 'B'들을 파란색으로 칠한다.

 

  따라서 입력으로 받은 문자열에서 연속된 'R'그룹과, 연속된 'B' 그룹의 수를 각각 세준다. (코드의 rCnt와 bCnt)

그리고 둘 중 작은 횟수에 +1(처음에 전체를 반대되는 색상으로 칠해줘야 하므로)을 한 값이 답이다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        String problem = br.readLine();
        int bCnt = 0;
        int rCnt = 0;
        char bf = '\0';
        for (int i = 0; i < n; i++) {
            char cur = problem.charAt(i);
            if (cur!=bf) {
                if (cur=='R') rCnt++;
                else bCnt++;
            }
            bf = cur;
        }
        System.out.println(Math.min(rCnt, bCnt) + 1);
    }
}