[백준] 20365 블로그2 - 그리디 + StringTokenizer JAVA

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

20365번: 블로그2

코드설명

그리디문제에 StringTokenizer를 활용하여 풀었습니다. ( Split을 활용해서 풀어도 됩니다. )

 

문제 예시의 

8
BBRBRBBR

를 보면, BBRBRBBR 이 있습니다.

여기서 색칠을 가장 적게하는 방법은 색의 그룹이 더 많은 색깔을 찾아서 한가지 색으로 모두 칠한뒤, 그룹의 개수가 더 작은 색깔의 그룹들을 칠하면 됩니다.

 

그 과정에서 그룹들의 개수를 구해줘야하는데 StringTokenzier함수와 Split 함수를 활용할 수 있습니다.

StringTokenizer의 함수로 

BBRBRBBR 이 존재할때 StringTokenizer를 활용하여 "R"을 구분자로 하여 나눈다면, BB, B, BB 이렇게 3가지로 나눌 수 있습니다. ('R'이 구분자이기에 'B' 로 된 그룹만 나옵니다.)

String questionList = br.readLine();
st = new StringTokenizer(questionList, "R", false);
while(st.hasMoreElements()) {
    st.nextToken();
    Bcnt++;
}

여기서 만약 StringTokenizer의 구분자도 함께 출력하고싶다면, 3번째 파라미터값에 true로 옵션을 설정할 수 있습니다.

그렇게 되면, BB,R,B,R,BB,R 이런 경우가 됩니다.

 

코드

가장 깔끔한 코드입니다.

이때 중요점은 before값으로 arr[-1]을 처리하여, 인덱스 에러가 없다는 점입니다.

일반적으로 arr[i] != arr[i+1] 이런식으로 처리한다면 마지막 Index 값 처리하는것이 상당히 까다로워집니다. 

또, 만약 N==1 이라면, 마지막 값 처리할때에도 복잡해지고요.

하지만, char before의 처음값을 ='X'로 초기화하여 arr[0] 부터 변화하는 값의 발생부터 개수를 모두 셀 수 있어서, Index 신경쓰지않고 처리가 가능합니다. (항상 그런건 아니지만, arr[i] != arr[i+1]의 형태보다는 arr[i-1] != arr[i] 형태로 처리하고 arr[0] 값을 먼저 처리하는 방안이 Index 오류가 없도록 하는데 더 좋은 것 같습니다.)

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
	private static int N, M, Q, K, X;
    private static char[] arr;
    private static char[] colored;
    private static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        arr = new char[N];
        arr = st.nextToken().toCharArray();

        char before ='X';
        int redCnt = 0, blueCnt = 0;
        for(int i=0; i<N; i++) {
        	if(arr[i] != before) {
        		if(arr[i] == 'R') redCnt += 1;
        		else if(arr[i] == 'B') blueCnt += 1;
        		before = arr[i];
        	}
        }
        
        answer = Math.min(redCnt, blueCnt) + 1;
        System.out.println(answer);
    }
    
}

 

StringTokenizer의 split 기능을 활용한 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    		
    	String questionList = br.readLine();
    	st = new StringTokenizer(questionList, "R");
    	
    	int Rcnt = 0;
    	int Bcnt = 0;
    	while(st.hasMoreElements()) {
    		st.nextToken();
    		Rcnt++;
    	}
    	
    	st = new StringTokenizer(questionList, "B");
    	while(st.hasMoreElements()) {
    		st.nextToken();
    		Bcnt++;
    	}    	
    	
    	if(Rcnt < Bcnt) {
    		answer = Rcnt + 1;
    	}
    	else if(Rcnt >= Bcnt) {
    		answer = Bcnt + 1;
    	}
    	
    	System.out.println(answer);
    	
    }
    
}

 

처음에 잘못 푼 코드입니다.

개수가 많은 것을 기준으로 모든 색깔을 칠한다음, 그 이후에 개수가 적은 숫자들을 채울려고 했습니다.

하지만, 

다음과 같은 반례가 존재합니다.

8
BBRRRRRB

오답 : 3
정답 : 2

저는 무조건 숫자가 많은것을 기준으로 하기에 잘못된 답을 반환합니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
	private static int N, M, Q, K, X;
    private static char[] arr;
    private static char[] colored;
    private static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        arr = new char[N];
        arr = st.nextToken().toCharArray();
        
        int BlueCnt = 0;
        for(int i=0;i<N;i++) {
        	if(arr[i] == 'B') BlueCnt += 1;
        }
        
        //만약 BlueCnt의 개수가 절반보다 크거나 많다면, BlueCnt로 모두 색칠한다.
        if(BlueCnt >= (N - BlueCnt)) {
        	answer += 1;
        	//이 로직안에서 이제 빨간색의 구간을 모두 구한다.
        	int idx = 0;
        	boolean isBeforeRed = false;
        	while(idx < N) {
        		if(arr[idx] == 'R') {
        			//만약 처음으로 빨간색을 마주쳤다면, 
        			if(isBeforeRed == false) {
        				isBeforeRed = true;
        			}
        		}else if(arr[idx] == 'B' ) {
        			//만약 파란색을 마주쳣다면, 이떄 이전에 빨간색 구간이었다면, 해당 구간 이전은 색칠해야 한다.
        			if(isBeforeRed == true) {
        				answer += 1;
        				isBeforeRed = false;
        			}
        		}
        		idx+=1;
        	}
        	if(isBeforeRed == true) {
        		answer += 1;
        	}
        }else if(BlueCnt < (N-BlueCnt)){
        	answer += 1;
        	//이 로직안에서 이제 빨간색의 구간을 모두 구한다.
        	int idx = 0;
        	boolean isBeforeBlue = false;
        	while(idx < N) {
        		if(arr[idx] == 'B') {
        			//만약 처음으로 파란색을 마주쳤다면, 
        			if(isBeforeBlue == false) {
        				isBeforeBlue = true;
        			}
        		}else if(arr[idx] == 'R' ) {
        			//만약 빨간색을 마주쳣다면, 이떄 이전에 빨간색 구간이었다면, 해당 구간 이전은 색칠해야 한다.
        			if(isBeforeBlue == true) {
        				answer += 1;
        				isBeforeBlue = false;
        			}
        		}
        		idx+=1;
        	}
        	if(isBeforeBlue == true) {
        		answer += 1;
        	}
        }
        
        System.out.println(answer);
        
    }
    
}