문자열 뒤집기

Q. 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자를 모두 0, 혹은 모두 1로 같게 만들어야 한다. 할 수 있는 행동은 연속된 하나의 숫자를 잡고 모두 뒤집는 것 이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.

 

input = "011110"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    count_to_all_zero = 0
    count_to_all_one = 0

    if string[0] == '0':
        count_to_all_one += 1
    elif string[0] == '1':
        count_to_all_zero += 1

    for i in range(len(string) - 1):
        if string[i] != string[i + 1]:
            if string[i + 1] == '0':
                count_to_all_one += 1
            if string[i + 1] == '1':
                count_to_all_zero += 1

    return min(count_to_all_one, count_to_all_zero)


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

 

"뒤집는 횟수" 에 대한 판단을 어떻게 할 수 있을까요?

이에 대해 손가락을 짚어가며 문자열을 따라가다보면, 바로 0에서 1로 변하는 순간 혹은 1에서 0으로 변하는 순간입니다.

0에서 1로 변한다는 소리는, 0으로 다시 뒤집어야 하니 전체를 0으로 만들기 위한 숫자가 +1 됩니다.

1에서 0으로 변한다는 소리는, 1로 다시 뒤집어야 하니 전체를 1로 만들기 위한 숫자가 +1 됩니다.

이 생각을 코드로 구현하시면 됩니다!

예를 들어서 01100 이라는 문자열을 조회할 때, 0번째 원소인 0 에서 1번째 원소 1 로 변경되었으니 전체를 0으로 만들기 위한 숫자가 +1 되었습니다. 그리고 2번째 원소인 1 에서 3번째 원소인 0 으로 변경될 때 전체를 1으로 만들기 위한 숫자가 +1 됩니다.

엇, 그런데 아까 봤던 숫자랑 다르네요? 모두 1으로 만드는 방법은 2 회 였는데.. 다시 위에 올라가서 보면, 0번째 원소와 1번째 원소도 뒤집어줘야 합니다.

이 경우를 인지하기 위해서는, 가장 첫 번째 원소가 0인지 1인지를 파악해줘야 합니다.

즉, 1) 뒤집어 질 경우 2) 첫 번째 원소가 0인지 1인지 에 대해서 계산하면, 모두 0으로 만드는 횟수와 모두 1로 만드는 횟수를 만들 수 있습니다. 그리고 0으로 만드는 횟수와 모두 1로 만드는 횟수 둘 중 최솟값을 반환해주면 됩니다!