난이도 : ●○○ | 풀이 시간 : 20분 | 메모리 제한 : 128MB | 기출 : 핵심 유형
문제
- 다솜이는 0과 1로만 이루어진 문자열 S를 갖고 있다.
- 다솜이는 이 문자열 S가 하나의 숫자로 구성되게 하고 싶다.
- 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다.
- 문자열 S가 주어졌을 때 다솜이가 해야 하는 행동의 최소 횟수를 출력하라.
입력조건
- 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어진다. S의 길이는 100만보다 작다.
출력조건
- 첫째 줄에 다솜이가 해야 하는 행동의 최소 횟수를 출력한다.
입력예시
0001100
출력예시
1
아이디어
- 모두 0으로 바꾸는 데에 필요한 횟수(cnt_0)와 1로 바꾸는 데에 필요한 횟수(cnt_1) 중 작은 것을 구하면 된다.
- S를 처음부터 끝까지 확인하면서 현재 값에서 다른 값으로 바뀔 때마다 cnt_0나 cnt_1을 증가시켜준다
코드
s = input()
cnt_0=0
cnt_1=0
# 0번째 값이 0이라면 모두 1로 바꾸기 위해서 최소 1번 뒤집어야 함
if s[0]=='0':
cnt_1+=1
else:
cnt_0+=1
for i in range(len(s)-1):
# 뒤집기를 해야 하는 경우
if s[i]!=s[i+1]:
# 0->1로 바뀌는 경우 현재 0 을 1로 바꾸기 위해 뒤집어야 함
if s[i]=='0':
cnt_1+=1
else:
cnt_0+=1
print(min(cnt_0,cnt_1))