[백준/Python] 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만보다 작다.

출력

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

풀이
묶여있는 부분들의 대표숫자들을 가지고 새로운 리스트를 구성하는 것을 원했다
예를들어, 1110011이라면 101처럼 표현해서 1의 개수와 0의 개수 중 더 적은 개수의 숫자를 뒤집으면 된다
따라서 s를 끝까지 순회하면서 이전 수와 달라지는 순간에 0과 1의 개수를 세주었다

다른 사람들이 제출한 코드를 살펴보니 나처럼 숫자가 직전 수와 달라지는 경우를 가지고 단 두줄로 풀어낸 사람들이 많았다

a = input()
print(max(a.count('01'), a.count('10')))

count가 $O(n)$의 시간복잡도를 갖는 함수라 실행 시간이 오래걸릴 줄 알았는데 굉장히 짧아서 놀랐다
아마 count 함수가 내부적으로 최적화되어있는 것이 원인이 아닐까 추측된다

코드

import sys

s = sys.stdin.readline().strip()
zero_num = 0
one_num = 0
cur = -1
for elem in s:
    if elem != cur:
        cur = elem
        if elem == "0":
            zero_num += 1
        else:
            one_num += 1
print(min(zero_num, one_num))