문자열 뒤집기
"뒤집는 횟수" 에 대한 판단을 어떻게 할 수 있을까?
문자열을 따라가다보면, 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로 만드는 횟수 둘 중 최솟값을 반환해주면 된다
문자열 뒤집기 코드
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)