백준 1439 - 뒤집기 ( Python )

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

1439번: 뒤집기

초급 그리디 알고리즘 문제

거스름돈을 거슬러주는 그리디 문제랑 다른경우이다. 

문제에서 2가지 경우를 나눠서 구분하므로 알고리즘도 2가지의 경우로 나눠서 짜야한다.

 

제한 시간 20분

 

풀이방법

1. 모두 1로 뒤집는 경우 혹은 0으로 뒤집는 경우로 나눠서 계산 후 각각 변수에 저장
2. 1로 뒤집는 경우  
    -> 첫번째 숫자가 0이면 카운트 + 1
    -> 1에서 0으로 바뀔 때 카운트 + 1

3. 0으로 뒤집는 경우

    -> 첫번째 숫자가 1이면 카운트 + 1 
    -> 0에서 1으로 바뀔 때 카운트 + 1

4. 변수 중 작은 수를 출력

 

string = input()

zero = 0
one = 0

if string[0] == '0':
    one += 1
elif string[0] == '1':
    zero += 1


    
for i in range( len(string) -1 ):
    if string[i] == '0' and string[i+1] == '1':
        zero +=1
    elif string[i] == '1' and string[i+1] == '0':
        one += 1
    
print(min(zero, one))

 

 

개선된 풀이법

- 시간이나 메모리는 동일하게 나왓지만 조금 더 깔끔한 풀이법

string = input()

zero = 0
one = 0

if string[0] == '0':
    one += 1
else:
    zero += 1


    
for i in range( len(string) -1 ):
    if string[i] != string[i+1] : #문자열이 바뀌는 경우
        if string[i+1] == '1': #0에 1로 바뀐경우
            zero +=1
        else:
            one += 1
    
print(min(zero, one))