[백준 온라인 저지] 뒤집기

문제 정의

• 문자열 S는 0, 1 구성되어 있고, 모든 숫자가 전부 같게 만들어야 한다.
• 뒤집을 때 연속된 숫자인 경우, 뒤집는 횟수는 1회로 한다.
  • 예를 들어, 00010일 시, 앞의 세 자리를 11110으로 뒤집는다면 이는 1회 뒤집는 것으로 간주
• 뒤집는 최소 횟수를 구하기

 

나의 풀이

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

import sys
S = sys.stdin.readline().strip()

result = [0, 0]

for i in [0, 1]:
    is_continue = False
    for idx, value in enumerate(S):
        if value != str(i):
            if is_continue == False:
                result[i] += 1
                is_continue = True
        else:
            is_continue = False   

print(min(result))

• 0과 1에 대해서 뒤집는 횟수를 각각 구하고 그 최솟값을 출력하도록 풀이
• is_continue 변수를 이용하여 연속된 구간인지 확인하고 뒤집는 횟수를 계산
  • 만일 S가 001100이고 이 문자열을 반복
    • 모두 0으로 바꾸기 위해서는 1이 연속된 구간의 갯수를 카운팅
    • index가 2부터 1이므로 is_continue는 True가 되고 앞으로 연속된 1이 나온다면 그 다음 index인 3까지 1이므로 is_continue는 True로 유지되 1이 연속된 구간이라고 치고 카운트 업을 하지 않음
    • 이후 0이므로 is_continue를 False로 두어 다음 1이 연속된 구간을 확인
  • 위의 방법을 그대로 이용해 모두 1로 바꾸기 위해 0이 연속된 구간의 갯수를 찾아냄
• 결과적으로 result에는 0과 1을 각각 그 숫자대로 바꾸기 위해 필요한 뒤집는 횟수가 적혀 있을 것이고 그 결과의 최솟값을 출력

 

Github : https://github.com/Limseunghyun95/code_test/blob/master/baekjoon/p_1439.py