[Baekjoon] 1439번 : 뒤집기

1. 문제

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

• 그리디 문제

// 문제
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다.
다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다.
다솜이가 할 수 있는 행동은
S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다.
뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

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

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

// 입력
첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

// 출력
첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

// 예제 입력 1
0001100

// 예제 출력 1
1

// 예제 입력 2
11111

// 예제 출력 2
0

// 예제 입력 3
00000001

// 예제 출력 3
1

// 예제 입력 4
11001100110011000001

// 예제 출력 4
4

// 예제 입력 5
11101101

// 예제 출력 5
2

2. 핵심 아이디어

• 문자열에 있는 숫자를 모두 0 혹은 1로 만들어야 함
• 문자열 S의 길이는 100만 이하이므로, 시간 복잡도는 O(N)에 해결해야 함
• 다음 두 가지 경우를 모두 계산
  • 모두 0으로 만드는 경우
  • 모두 1로 만드는 경우

3. Python 문제풀이

# 방법 1
import sys
input = sys.stdin.readline

data = input().rstrip()
count0 = 0
count1 = 0

if data[0] == '1' :
  count0 += 1
else :
  count1 += 1

for i in range(len(data) - 1) :
  if data[i] != data[i + 1] :
    if data[i + 1] == '1' :
      count0 += 1
    else :
      count1 += 1

print(min(count0, count1))

# 방법 2
import sys
input = sys.stdin.readline

data, count = input().rstrip(), 0

for i in range(1, len(data)) :
  if data[i] != data[i-1] :
    count += 1

print((count + 1) // 2)

4. Java 문제풀이

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String d = sc.next();
    char[] data = d.toCharArray();
    int count0 = 0, count1 = 0;

    if (data[0] == '1') {
      count0++;
    } else {
      count1++;
    }

    for (int i=0; i<data.length-1; i++) {
      if (data[i] != data[i+1]) {
        if (data[i+1] == '1') {
          count0++;
        }
        else {
          count1++;
        }
      }
    }
    System.out.println(Math.min(count0,count1));
  }
}