문제 :
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만드려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어, S = 0001100일 때는 다음과 같다.
1. 전체를 뒤집으면 1110011이 된다.
- 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 두 번 만에 모두 같은 숫자로 만들 수 있다.
하지만 처음부터 4번째, 5번째 문자열 00을 11로 뒤집으면 한 번만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어질 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력해라
-
입력조건
첫째 줄에 0과 1로만 이루어진 문자열 S가 주어진다. S의 길이는 100만 보다 작다. -
출력조건
첫째 줄에 다솜이가 해야 하는 행동의 최소 횟수를 출력한다.
입력예시 :
0001100
출력예시 :
1
구현코드:
import java.util.*;
public class Main6{
public static void main(String args[]){
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
int count = 0;
int num = s.charAt(0) - '0';
for(int i = 1 ; i < s.length();i++){
if(num != (s.charAt(i) - '0')){
count++;
num = (s.charAt(i) - '0');
}
}
if(count%2 != 0 && count != 1) System.out.println(count/2+1);
else System.out.println(count/2);
}
}코드해석:
이 문제는 0 으로든 1으로든 전체를 총합시키는 문제이다. 연속되는 같은 수는 한번에 변경이 가능하다.
그렇다면 이문제를 구간으로 보는 것도 좋은 방법일 것이라 생각했다.
만약 1000110001 이라는 수가 있다고 가정하자. 2번바꾸어 모든 수를 1로 만들 수있다.
나는 이것을 1 000 11 000 1 구간으로 보았다. 즉 수가 바뀌는 번 수를 세어보자. 4번 바뀌는 것을 볼 수있다. 우리는 (바뀌는 번수 / 2) 를 하면 된다. 그럼 홀수는 ? 1일때는? 으로 생각할 수있기 때문에 그경우도 나누어 주었다. 홀 수일경우엔 +1을 해주었고 1일때는 제외하고 했다.
