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

문자열 뒤집기

난이도 : 下 풀이 시간 : 20분

시간 제한 : 2초 메모리 제한 : 128 MB

 

---

 

해답

 

s = input()

allzero, allone = 0, 0

for i in range(len(s)-1):
    if s[i] != s[i+1]:
        if s[i+1] == '1':
            allzero = allzero + 1
        else:
            allone = allone + 1

print(min(allzero, allone))

---

예시

 

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))

---

해설

 

전부 0으로 바꾸는 allzero와 전부 1로 바꾸는 allone 두 가지의 경우 중 더 적은 횟수를 가지는 경우를 계산하면 됩니다.