[코딩테스트] 백준 1439번: 뒤집기

-문제: https://www.acmicpc.net/problem/1439

1439번: 뒤집기

알고보니 엄청 쉬웠던 문제 

 

-정답풀이: 

n=input()
cnt=0

for i in range(len(n)-1):
	if n[i] != n[i+1]:
		cnt+=1  
print(cnt//2)

1의 묶음은 1로 생각하고, 0의 묶음은 0으로 생각하면 00011000은 010으로 봐도 무관하다. 길이에 관계없이 문자가 바뀌는지만 보면 되기 때문.

 

0과 1 은 0번 바꾸고, 길이가 1 -> 바뀌는 구간 0번이라 0번 바꾼다

10,01 은 1번 바꾸고, 길이가 2 -> 바뀌는 구간 1번, 1번 바꾼다 

010은 1번 바꾸고, 길이가 3 -> 바뀌는 구간 2번, 1번 바꾼다

0101은 2번 바꾸고, 길이가 4 -> 바뀌는 구간 3번, 2번 바꾼다

01010은 2번 바꾸고, 길이가 5 -> 바뀌는 구간 4번, 2번 바꾼다 

010101은 3번 바꾸고, 길이가 6 -> 바뀌는 구간 5번, 3번 바꾼다

0101010은 3번 바꾸고, 길이가 7  -> 바뀌는 구간 6번, 3번 바꾼다 

따라서 바뀌는 구간 수를 cnt라고 한다면, 바꾸는 최소 횟수는 (cnt+1)//2임을 알 수 있다. 

 

-다른 풀이

숫자가 0,1 밖에 없으므로 숫자가 바뀌는 지점을 기준으로 생각하면된다

해당위치에 있는 숫자가 0이면 모두 1로 바꾸는 경우(one)를 세고, 

숫자가 1일 때 모두 0으로 바꾸는 경우(zero)를 센다 

 

0이 1로 바뀌는 횟수와 1이 0으로 바뀌는 횟수 중 최솟값을 출력하면 정답이다

data=input()
zero=0 #전부 0으로 바뀌는 경우
one=0 #전부 1로 바뀌는 경우

if data[0]=='1':
	zero+=1
else:
	one+=1
    
for i in range(len(data)-1): #0부터 len(data)-2까지 반복문 돌림 -> 실제로는 1부터 len(data)-1까지 반복문 수행
	if data[i] != data[i+1]:
    	if data[i+1] =='1': #i번째가 '0'이었다는 의미
        	zero+=1
        else:
        	one+=1
print(min(zero,one))