[BOJ 1439] 뒤집기 (Python)

kimdukbae·2021년 4월 11일
0

문제

링크



풀이

  1. 연속된 0의 덩어리 갯수와 연속된 1의 덩이리 개수를 구한다.

  2. 그 중 최솟값이 정답이다.

예제를 통해 올바른 풀이인지 확인해보자.

(Ex) S=00011000

연속된 0의 덩어리 -> 2개
연속된 1의 덩어리 -> 1개

이 중 최솟값은 1이다. 즉, 답은 1이 된다. 왜냐하면 '11'의 덩어리만 0으로 바꿔주면 '00000000'이 되어 1번 만에 모두 같은 숫자로 만들 수 있기 때문이다.



코드

import sys

input = sys.stdin.readline
S = input().rstrip()    # 주의! rstrip() 안하면 개행문자 추가되서 길이 + 1이 됨
count = [0] * 2 # 카운팅 배열

# 0 -> 1 or 1 -> 0 으로 바꾸는 부분 체크
for i in range(len(S) - 1):
    if S[i] == '0' and S[i] != S[i + 1]:
        count[0] += 1
    elif S[i] == '1' and S[i] != S[i + 1]:
        count[1] += 1

# 마지막 덩어리가 연속된 0의 덩어리인지 혹은 1의 덩어리인지 확인
if S[len(S) - 1] == '0':
    count[0] += 1
else:
    count[1] += 1

print(min(count))
profile
A Student of Computer Science

0개의 댓글