문제
0과 1로만 이루어진 문자열이 주어졌을 때, 연속된 같은 숫자 구간을 한 번에 뒤집을 수 있다. 모든 숫자를 같게 만들기 위한 최소 뒤집기 횟수를 구하라.
입력
첫째 줄에 0과 1로만 이루어진 문자열이 주어진다 (길이 1 이상 1,000,000 이하).
출력
최소 뒤집기 횟수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
0001100 | 1 |
풀이
0 그룹의 수와 1 그룹의 수 중 작은 쪽을 뒤집는다.
StringTokenizer로 "0"을 구분자로 사용하여 1 그룹의 수를 센다- "1"을 구분자로 사용하여 0 그룹의 수를 센다
- 두 그룹 수 중 최솟값이 정답이다
핵심 아이디어: 모든 숫자를 0으로 통일하려면 1 그룹 수만큼, 1로 통일하려면 0 그룹 수만큼 뒤집어야 하므로, 더 적은 쪽을 선택한다.
코드
package ASP_study.day299;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day265BOJ1439뒤집기 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
StringTokenizer st1 = new StringTokenizer(s, "0");
StringTokenizer st0 = new StringTokenizer(s, "1");
System.out.println(Math.min(st1.countTokens(), st0.countTokens()));
br.close();
}
}복잡도
- 시간: O(N)
- 공간: O(N)