[백준 / solved ac] [Python] 1439 뒤집기

1439번: 뒤집기 (acmicpc.net)

1439번: 뒤집기

문제

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

출력

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

---

접근법

뒤집기 최소 횟수는뒤집을 문자를 '0', '1' 중에 선택한 후, 두 경우에서 최솟값을 찾으면 된다고 생각했다.

1. 뒤집기 최소 횟수를 적당히 큰 수로 설정하기 => min_cnt
2. ('0', '1') 중에 뒤집을 문자 선택하기 => num
3. 문자 선택 후 뒤집는 횟수와 문자의 위치를 초기화 => cnt, start
4. 선택한 문자가 나오면 start에 인덱스 값을 넣어줌 
5. 현재는 선택한 문자가 나오지 않았지만 그 전에 선택한 문자가 나온 경우, cnt를 1 증가시키고
문자의 위치를 초기화
6. 반복문 종료 후, start가 초기화되지 않았다면, start부터 마지막 인덱스까지가 선택된 문자이므로,
뒤집는 횟수 1 증가시킴
7. min_cnt와 cnt를 비교해, 최소 횟수를 갱신해줌

 

풀이1

# 30616 KB / 40 ms
def find_cnt():
    length = len(binary_str)
    min_cnt = length
    for num in ('0', '1'):
        cnt, start = 0, -1
        for i in range(length):
            if binary_str[i] == num:
                if start == -1:
                    start = i
            elif start != -1:
                cnt += 1
                start = -1
        if start != -1:
            cnt += 1
        if min_cnt > cnt:
            min_cnt = cnt
    return min_cnt

binary_str = input()
print(find_cnt())

 

풀이2

# 30616 KB / 36 ms
# 함수 인자를 추가
def find_cnt(binary_str):
    length = len(binary_str)
    min_cnt = length
    for num in ('0', '1'):
        cnt, start = 0, -1
        for i in range(length):
            if binary_str[i] == num:
                if start == -1:
                    start = i
            elif start != -1:
                cnt += 1
                start = -1
        if start != -1:
            cnt += 1
        if min_cnt > cnt:
            min_cnt = cnt
    return min_cnt
    
binary_str = input()
print(find_cnt(binary_str))