[그리디] 문자열 뒤집기 (파이썬)

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

할 수 있는 행동은 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. (1을 0으로 또는 0을 1로)

해야 하는 행동의 최소 횟수를 구하세요.

---

s = list(input())
cnt = 0

print(s)

#1 뭉텡이
cnt_1 = 0
#0 뭉텡이
cnt_0 = 0

if s[0] == '1' : cnt_1 += 1
elif s[0] == '0' : cnt_0 += 1

i=0
for i in range(len(s)-1):
  if s[i] != s[i+1]:
    if s[i+1] == '1': cnt_0 += 1
    elif s[i+1] == '0': cnt_1 += 1

print(cnt_1, cnt_0)
print(min(cnt_1, cnt_0))

이 문제를 풀 때 엄청 골머리 앓았는데, 

처음에 생각했던 아이디어는 다른 숫자가 나오기 시작하는 인덱스와 그 숫자가 끝나는 인덱스를 알아내서 뒤집는 ? 그런 방식을 생각했었다. 그런데 그렇게 생각하면 너무 복잡하기도 하고 횟수만 세는 거지 굳이 직접 숫자를 뒤집을 필요가 없기 때문에 다른 방법을 생각했다.

 

0으로 이루어진 뭉텅이와 1로 이루어진 뭉텅이의 수를 센 후에

더 적은 뭉텅이 수를 리턴하는 방식을 이용하였다.