[BOJ 1439, Python 3] 뒤집기

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

1439번: 뒤집기

 

풀이

 

S의 길이가 100만이면 O(N) 이나 O(NlogN)이 최대인 것을 알 수 있다.

그래서 O(N)으로 살펴보면 나오는 방법은 1을 전부 뒤집어서 000000으로 바꾸거나, 0을 전부 뒤집어서 111111로 바꾸면 되는 것을 충분히 추론할 수 있다.

 

그래서 1을 전부 뒤집을 때 뒤집는 횟수, 0을 전부 뒤집을 때 뒤집는 횟수를 구해 최솟값을 답으로 출력하면 된다.

 

코드

s = input()
ans = [0, 0]
x = s[0]
for i in range(1, len(s)):
    if x != s[i]:
        if x == '0': ans[0] += 1
        else: ans[1] += 1
        x = s[i]
if x == '0': ans[0] += 1
else: ans[1] += 1
 
print(min(ans))