python | 1439번. 뒤집기 | greedy(그리디)

📒 문제

---

 

🤸‍♀️ 문제 분석

---

연속되는 숫자의 묶음이 적은 수를 뒤집는 것이 유리하다.

💡 즉, 문자열에서 모든 수를 0으로 만드는 경우와 1로 만드는 경우를 비교하여 둘 중 행동이 적은 값을 선택하면 된다.

 

구하는 방법은 코드에서 확인할 수 있다.

 

 

🧮코드

---

def string_swap(numbers):
    
    # 0혹은 1의 문자열을 뒤집어서 1또는 0으로 통일되기 위한 횟수
    swap_to_zero = 0
    swap_to_one = 0
    
    # 매번 비교대상의 숫자 (처음에는 맨 앞 숫자)
    temp = numbers[0]
    
    # 처음에는 맨 앞 숫자값가 아닌 값을 1로 세팅
    if temp == '0':
        swap_to_one = 1
    else:
        swap_to_zero = 1
    
    # 입력 숫자를 첫번째 숫자 제외하고 하나씩 확인
    for n in numbers[1:]:
        
        # 1) 0을 1로 만들기
        # -> n이 0이고, 비교대상 숫자와 다르면 swap_to_one+1
        # -> 비교대상 숫자와 동일할 경우 한번에 뒤집을 수 있기 때문에 +1 안해준다
        if n == '0' and temp != n:
            swap_to_one += 1
            
        # 2) 1을 0으로 만들기    
        elif n == '1' and temp != n:
            swap_to_zero += 1
        
        # 비교대상 숫자를 다시 현재값으로 할당
        temp = n
     
    # print(f'swap_to_zero={swap_to_zero}')
    # print(f'swap_to_one={swap_to_one}')
    
    return min(swap_to_one, swap_to_zero)
    
    
n = input()
print(string_swap(n))