문제 출처 : https://www.acmicpc.net/problem/1439
난이도 : 실버 5

문제 파악

'0'과 '1'로 이루어진 문자열 S를 입력 받는다.

그리고 1 덩어리, 또는 0 덩어리를 뒤집을 수 있는데
최소 횟수로 뒤집어서 다 같은 숫자로 만들어야 한다.

어떻게 풀 수 있을까?

해결 아이디어

1. 결국 내게 필요한 것은 1 덩어리, 0 덩어리기에 문자열 S를 압축 시켜 준다.

   111111 => 1로
   1111111111000000000000111111 => 101로

2. 1과 0의 개수를 세어준다.
   만약 1이 2개 0이 1개라면,
   0을 한번 뒤집는게 1을 두번 뒤집는 것보다 효율적일 것이다.

   그러니 1과 0의 개수 중 더 작은 개수만큼만 뒤집어 주면 된다.

이렇게 풀 수 있었지만 마지막 예외처리 하나를 해주어야 한다.

만약 S가 이미 1 덩어리 or 0 덩어리 로만 이루어져있던 녀석이라면
뒤집을 필요 없이 0을 출력해주어야 하지만, 위 풀이대로 라면 1이 출력된다.

그러니 덩어리의 길이가 1이라면, 0을 출력해주도록 해준다.

해답 코드

import sys
input = sys.stdin.readline
from collections import Counter

S = list(input().strip())

# 1과 0으로 구성된 문자열
# 압축해주어 1들의 뭉탱이 개수와 0들의 뭉탱이 개수 중 더 작은 개수 출력하기.
zipped = []

prev = -1

for cur in S:
    if cur == prev:
        prev = cur
        continue
    else:
        zipped.append(cur)
        prev = cur

cnt = Counter(zipped)

if len(cnt) == 1:
    print(0)
else:
    print(min(cnt.values()))