[백준] 1439 뒤집기

새싹·2021년 10월 6일
0

알고리즘

목록 보기
17/49

📌문제 링크

https://www.acmicpc.net/problem/1439

💡 문제 풀이

0이 연속하는 구간, 1이 연속하는 구간의 개수 중 더 작은 값만큼 뒤집으면 정답이다.

연속하는 구간을 찾기 위해서 문자열 s의 길이만큼 반복해 0에서 1로 변하는 구간 또는 1에서 0으로 변하는 구간이면 개수를 셌다.
구간의 끝에서 변하면 개수를 셌기 때문에 변화가 없는 문자열의 맨 마지막에서 0인지 1인지에 따라서 추가로 개수를 카운트했다.

문자열 길이 n만큼 반복하기 때문에 시간초과가 뜰까봐 걱정했는데 무난하게 통과했다. (68ms 나옴)

📋코드

# 1439 뒤집기
s = input()

zero = 0  # 0이 연속하는 구간의 개수
one = 0  # 1이 연속하는 구간의 개수

for i in range(len(s) - 1):
    # 0에서 1로 변할 때
    if s[i] == '0' and s[i+1] == '1':
        zero += 1
    # 1에서 0으로 변할 때
    elif s[i] == '1' and s[i+1] == '0':
        one += 1

# 문자열의 마지막에서 구간 카운트 추가
if s[-1] == '0':
    zero += 1
else:
    one += 1

# 더 작은 값만큼 뒤집음
print(min(zero, one))

0개의 댓글