1439 뒤집기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	
	public static void main(String[] args) throws IOException {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		String input = st.nextToken();	
		String [] word = input.split("");
		
		int N = word.length;
		
		Queue<String> data = new LinkedList<>();
		
		for(int i = 0; i<N;i++) {
			data.add(word[i]);
		}
	
		String value = data.peek();
		
		int one=0;
		int zero=0;
	
		while(N -->-1) {
			
			if(value.equals(data.peek())) {
				data.remove();
				
			} else if(!value.equals(data.peek()) || data.isEmpty()){
			
			if(value.equals("1")) {
				one++;
			
			}else {
				zero++;
			   }			
			
			value = data.poll();
			}
		}
		
		int min = Math.min(one, zero);
		System.out.println(min);
	}
}

 

 

# 해결법

 

문제에서 알려주었듯이, 연속된 숫자들만 한 번에 뒤집을 수 있기 때문에

예제 0001100 에서는

<첫번째> 앞의 000 을 한 번 뒤집고, 뒤의 00을 뒤집으면 1111111으로 완성이 되고,

<두번째> 가운데 있는 11을 한 번 뒤집으면 0000000 으로 완성된다.

 

내가 이 문제에서 생각해 낸 방법은, 뭉쳐있는 1과 0의 카운트를 세는 것이다.

즉, 0001100 에서는 맨 앞에 0이 세개 뭉쳐있다. 그러면 0의 카운트를 하나 증가시킨다.

그 다음 1이 2개 뭉쳐있다. 그러면 1의 카운트를 하나 증가시킨다. 

그 다음 0 이 2개 뭉쳐있다. 그러면 0의 카운트를 하나 더 증가시켜서 0의 카운트는 총 2가 된다.

즉, 1의 카운트는 1개, 0의 카운트는 2개가 된다.

 

위에서 

<첫번째> 방법에서는 0과 관련하여 2번 뒤집어서 완성되고, ----------> 0의 카운트 수

<두번째> 방법에서는 1과 관련하여 1번 뒤집어서 완성되었다. --------> 1의 카운트 수

 

이렇게 카운트를 세서 작은 값으로 리턴하면 완성된다.

 

#풀이

 

입력값이 주어지면 한글자씩 분리해서 큐에 집어넣도록 했다.

즉, 입력값이 0001100으로 주어지면 0 0 0 1 1 0 0 으로 분리해서 큐에 집어넣는다.

 

그런데 StringTokenizer 로 한글자씩 분리하기에는 입력값에 구분자가 없어서(공백이나 기호 등)

일단 문자열(input)으로 받고,

 

	String input = st.nextToken();

한글자씩 쪼개서 배열(word)에 집어넣은 다음에

 

	String [] word = input.split("");

다시 큐(data) 에 집어넣었다.

 

		
		for(int i = 0; i<N;i++) {
			data.add(word[i]);
		}

 

그런 다음 위에서 설명한대로, 뭉쳐있는 수의 카운트를 세도록 했다.

 

특히 내가 카운트를 셀때,

0001100에서

맨 처음 0 (이 값을 변수 value 값으로 지정) 이 나왔을 때 카운트를 세는 게 아니라,

0 0 0 1 이나오면 세도록했다.

즉 원래 0이 나오다가,

큐에서 peek 로 맨 위의 값을 참조했을때,

다른 수 1이 나오면 0의 카운트를 세도록했다.

 

그리고 나서는 value 값을 1로 바꿔준 뒤 위의 과정을 반복.

 

그런데 문제는 맨 마지막의 경우이다.

00 인데, 이 경우는 다음 수가 나오는 게 아니라, 그냥 이대로 끝난다.

그래서 while 문에서 N을 -1 까지 하도록 하고,

큐에 값이 없을 때도 카운트를 증가시키도록 하여,

정상적으로 0의 카운트가 증가되도록 했다.