백준 1439 - 뒤집기 (자바 - 그리디)

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

1439번: 뒤집기

 

* 문제 요약

0과 1로만 이루어진 문자열 S 를 가지고 있다. 이 문자열 S 에 있는 모든 숫자를 전부 같게 만드려고 한다.

할 수 있는 행동은 S 에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다.

뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 말한다.

 

예를 들어 S = 0001100 일 때,

1. 전체를 뒤집으면 1110011 이 된다.

2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111 이 되어서 2번만에 모두 같은 숫자로 만들 수 있다.

하지만 처음부터 4번째 문자부터 5번째 문자까지 뒤집으면 한번에 0000000 이 되어서 1번만에 모두 같은 숫자로 만들 수 있다.

 

 

* 입력

- 길이가 100만 보다 작은 문자열 S 가 주어진다.

 

* 출력

- 해야하는 행동의 최소 횟수를 출력한다.

 

* 예시

 

* 해결 과정

1. 행동 횟수를 최소화 해야 하므로 문자열에서 0, 1 의 집합군 갯수 중 더 작은 값이 정답이다.

2. 0, 1 의 집합군 갯수가 서로 같은 경우 동일한 숫자를 그대로 출력한다.

3. 하나의 숫자로만 이루어져 있으면 문자열을 뒤집을 필요가 없으므로 0 을 출력해준다.

(0, 1 의 집합군 중 하나라도 갯수가 0 이라면 0 을 출력해준다.)

 

- 0 과 1 의 집합군 갯수를 표현할 변수 zeroCount, oneCount 를 초기화해준다.

- 문자열에서 첫번째 문자가 무엇이냐에 따라 집합군의 갯수를 더해준 다음, 현재 탐색단계에서

집합군이 무엇인지 current 에 저장해두고 난 후 반복문을 수행한다.

- current 에 들어있는 값과 현재 문자열에서 탐색하고 있는 값이 서로 다를 경우

    1. current 의 값을 현재 문자열에서 탐색하고 있는 값으로 변경해준다.

    2. current 의 값이 1인 경우 숫자 1의 집합군을 표현하는 변수 oneCount 의 값을 1 늘려준다.

    3. current 의 값이 0 인 경우 숫자  0 의 집합군을 표현하는 변수인 zeroCount 의 값을 1 늘려준다.

 

- 반복문이 끝나고 난 후 zeroCount 와 oneCount 의 값이 무엇이냐에 따라 정답을 출력해준다.

1. zeroCount, oneCount 중 하나가 0 이라면. 즉, 문자열이 0, 1 둘 중 한 가지로만 이루어져 있다면 0 을 출력한다.

2. zeroCount, oneCount 의 값이 같다면 둘 중 아무값이나 출력해준다.

3. zeroCount, oneCount 의 값이 서로 다르면서 0 이 아니라면 둘 중 더 작은 값을 출력해준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public 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));
		
		char[] array = br.readLine().toCharArray();
		int oneCount = 0;
		int zeroCount = 0;
		char current = array[0];
		if(current == '1')
			oneCount++;
		else if(current == '0')
			zeroCount++;
		
		for(int i = 1; i < array.length; i++) {
			if(current != array[i]) {
				current = array[i];
				if(current == '1')
					oneCount++;
				else if(current == '0')
					zeroCount++;
			}
		}
		
		if(zeroCount == 0 || oneCount == 0)
			bw.write(0 + "\n");
		else if(zeroCount == oneCount){
			bw.write(zeroCount + "\n");
		}
		else {
			if(oneCount > zeroCount)
				bw.write(zeroCount + "\n");
			else if(oneCount < zeroCount)
				bw.write(oneCount + "\n");
		}
		
		bw.flush();
		bw.close();
	}
}

 

현재 탐색단계에 맞춰 각 숫자의 집합군 갯수를 검사한뒤, 검사한 집합군의 갯수가 어떻냐에 따라 문제의 조건에 맞춰 정답을 출력해준다.

매 반복마다 현재의 선택이 이후의 단계에 영향을 미치지 않으므로(각 숫자의 집합군 갯수 찾기) 그리디 알고리즘 문제라고 할 수 있다.