[ Baekjoon - 10/15 ] - 20365번: 블로그2

• 문제 링크 : https://www.acmicpc.net/problem/20365

20365번: 블로그2

• 소요 시간 : 40분
• <카카오의 데이터센터 문제로, 15일에 풀었지만 바로 올리지못했다..>

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 1024MB
   • 문제
     • 문제의 수(0≤N≤500,000), 문제를 칠하는 색상은 각각 B아니면 R
     • 한 문제 이름을 덧칠해도 마지막 칠한색만 보여질때, 최소로 문제를 칠할 수 있는 횟수를 출력
   • 이해
     
     • 문제에서 B와 R중 많은색을 먼저 배경에 칠해두고, 적게 칠해진 색을 칠하는 방식으로 짜야한다고 생각했다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

      
   • 위에서 언급한것 처럼 많은색은 한번만 크게 칠해버리면 되므로, 적게 칠해진 색깔의 문제만 어떻게 최소로 칠할 수 있을지만 정하면 될것같았다.
3. 문제를 어떻게 해결할 것인가
   • 1st 접근 - B이면 1이상의 양수, R이면 -1이하의 음수로 각 번호를 매긴 뒤 칠해야할 횟수를 정하는 방법)
     
     • B가 가장 처음에 나왔거나, 이전에 B가 아니었으면 1을 주고, B뒤에 B가 나오면 2,3,4... 로 증가한다.
     • R도 이와 같은 방식으로, 0번째거나 이전에 R이 아니라면 -1을 주고 R뒤에 R이나오면 -2,-3... 로 감소한다.
     •  
   • 2nd 접근 - 가장 많은 색을 먼저 칠한뒤, 적은색의 제목을 칠하는 방법)
     
     1. B가 인접하지 않은 묶음 개수를 구해서 이를 R 개수와 비교하는 방법
        • 이 접근이 말로 설명했을때는 맞는것같지만..  R개수를 N-B개수 라고 생각한 착오로 두번 틀렸습니다를 경험했다. 반복문 한번으로 글자가 B이면 B개수+=1하는게 아닌, 연속된 B를 묶는다는 전제에서의 인접하지 않은 B의 개수이므로 N-B개수로는 R개수를 구할수 없다!
        • 이게 아니라면 결국 처음과 같아진다. 
     2. 반복문을 수행하며 B의 개수, R의 개수를 같이 세는 방식
        • 연속 여부를 따지기 위해, 각 B와 R이 연속되지않은 개수를 구해서, 그중 작은값에 +1을 하면 답이된다.
        • +1을 하는 이유는, 많은 색상으로 전체문제를 칠하기 위함이다. 
4. 위 계획을 검증
   • 3번에서 검증까지 시도했다.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.util.*;
        import java.io.*;
        
        public class Main{
            static int N,blueCnt=0;
            static String color;
            static int[] curCnt = {0,0};
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
                N = Integer.parseInt(br.readLine());
                color = br.readLine();
        
                if (color.charAt(0)=='R')
                    curCnt[0]=1;
                else
                    curCnt[1]=1;
        
                for (int n = 1; n < N; n++) {
                    if(color.charAt(n) != color.charAt(n-1)){
                        if(color.charAt(n)=='R')
                            curCnt[0]+=1;
                        else
                            curCnt[1]+=1;
                    }
                }
        
                System.out.println(Math.min(curCnt[0], curCnt[1])+1);
            }
        }

• 결과

입력 문자열에서의 B의 개수는 N - R의 개수가 맞지만, B를 칠해야하는 횟수 = N- R을 칠해야하는 횟수가 아니라는 점을 바로 파악하지 못해서 생긴 오류였다. 쉬운문제일수록 생각하지않고 제출해서 더 많이 틀리는것같다..ㅜ