백준 1439: 뒤집기 - Greedy

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

1439번: 뒤집기

처음에 stack에 1을 넣어주고, 문자열을 하나씩 보면서 값이 바뀌면 stack에 1을 추가합니다.

ex) 001100111000 => [1, 1, 1, 1, 1] = [0그룹, 1그룹, 0그룹, 1그룹, 0그룹] 혹은 [1그룹, 0그룹, 1그룹, 0그룹, 1그룹]

 

값이 바뀌지 않았다면 모두 0이거나 1이기 때문에 뒤집어줄 필요가 없기 때문에 0을 출력합니다.

값이 바뀌었다면 stack 길이에서 2를 나눈 값을 출력해줍니다.

 

000111000 일 경우 stack에 [1,1,1]이 됩니다. 이경우 가운데 1이 의미하는 '111'만 뒤집어주면 됩니다.

01100111의 경우 [1,1,1,1] 이 되고, 이 경우에도 두번째 '11'과 네번째 '111' 두 개만 뒤집어 주면 됩니다. (0을 뒤집어도 상관이 없음)

 

stack의 길이가 짝수인 경우에는 0 그룹의 수와, 1 그룹의 수가 동일하기 때문에 둘 중 어느 것을 뒤집건 상관이 없습니다.

stack의 길이가 홀수일 경우에는 0그룹과 1그룹 중 그룹의 수가 더 적은 것을 뒤집어주면 됩니다.

stack[1::2]의 길이가 곧 답이 되는데 이는 stack의 길이에서 2를 나눈 것과 같습니다. (짝수일 때도 마찬가지)

 

각 그룹의 수를 세는 변수를 따로 두어 카운트를 해주고 마지막에 더 적은 값을 출력하는 방식으로 풀어도 되긴합니다.

 

from sys import stdin
input = stdin.readline

s = input().rstrip()

group = [1]
current = s[0]
for ss in s[1:]:
    if ss != current:
        group.append(1)
        current = '1' if current == '0' else '0'

if len(group) == 1: # ex) 00000000, 11111111
    print(0)
else:
    print(len(group)//2)