[이코테] 3일차 Greedy _ 문자열 뒤집기

[1]문자열 뒤집기 🟢

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있습니다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 합니다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것입니다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미합니다.

1. 문자열 S가 주어졌을 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력하세요.

입력 조건

• 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어집니다.S의 길이는 100만 보다 작습니다.

출력 조건

• 첫째 줄에 다솜이가 해야 하는 행동의 최소 횟수를 출력합니다.

🛠Problem Approach

✅ 최소 횟수 → 뭉텅이 개수가 적은 애를 뽑아야지 → 플립이 되는 횟수의 절반(양 끝에서 모두 바뀌므로)이 최소

🔑Solution

s = input()

cur = s[0]
flip_cnt = 0

for i in s[1:]:
  if cur != i:
    flip_cnt += 1
    cur = i

if flip_cnt % 2 == 0:
  print(flip_cnt//2)
else:
  print((flip_cnt+1)//2)

# 다른 풀이
    
data = input()
count0 = 0
count1 = 0

if data[0] == '1':
  count0 += 1
else:
  count1 += 1

for i in range(len(data)-1):
  if data[i] != data[i+1]:
    if data[i+1] == '1':
      count0 += 1
    else:
      count1 += 1

print(min(count0,count1))