그리디 알고리즘 : 문자열 뒤집기 - 파이썬 (python)

- 입력 조건

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

- 출력 조건

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

 

테스트케이스) 0001100 -> 1

 

* 방법1

아이디어: 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중에서 더 적은 횟수를 가지는 경우를 계산한다.

예를 들어 문자열이 "0001100"이라고 가정하면 '모두 0으로 바꾸는 경우'의 횟수는 1이고 '모두 1으로 바꾸는 경우'의 횟수는 2이다.

두 값 중 적은 횟수인 1을 출력하면 된다.

data = input()
count0 = 0 #전부 0으로 바꾸는 경우
count1 = 0 #전부 1로 바꾸는 경우

#첫 번째 원소에 대해서 처리
if data[0] == '1':
    count0 += 1
else:
    count1 += 1

#두 번째 원소부터 모든 원소를 확인하며
for i in range(len(data)-1):
    if data[i] != data[i+1]:
        #다음 수에서 1로 바뀌는 경우
        if data[i+1] == '1':
            count0 += 1
        #다음 수에서 0으로 바뀌는 경우
        else:
            count1 += 1

print(min(count0, count1))

 

 

 

github.com/501501/codingTest/commit/689375df8b752db3eedcf6e57fc85777f2ccff5a

#11-03 · 501501/codingTest@689375d