[BOJ/Python] 1439번: 뒤집기 || 그리디, 문자열

백준 1439 뒤집기 파이썬

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만보다 작다.

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

❍ 예제

❏ 문제 풀이

예를 들어 문자열이 “11101101”로 주어진 경우, 11101101 ⇒ 11111101 로 한 번 변경을 해주고, 11111101 ⇒ 11111111로 한 번 더 변경을 해주어 최종 결과는 2로 출력된다.
“11101101”에서 1로 이루어진 묶음과 0으로 이루어진 묶음의 각 개수는 3개와 2개이다. 따라서, 묶음의 수가 더 적은 0을 2번 변경해주면 모두 동일한 수로 바꾸어줄 수 있다.

❍ CODE

import sys

input = sys.stdin.readline

s = input()

pre_num = s[0]  # 이전 숫자를 주어진 문자열의 첫 숫자로 설정
zero = 0 # 0의 묶음 개수
one = 0  # 1의 묶음 개수

for i in range(1, len(s)):  # 주어진 문자열의 두 번째 수부터 탐색 시작
    if pre_num != s[i]:     # 이전 숫자와 동일하지 않다면, 묶음이 종료되었음을 의미
        if pre_num == '0':  # 이전 숫자가 0이었다면 0의 묶음 개수를,
            zero += 1
        else:               # 그렇지 않다면, 1의 묶음 개수를 1 증가
            one += 1
        pre_num = s[i]      # 이전 숫자를 현재 비교하던 수로 재설정
print(min(zero, one))       # 0과 1의 각 묶음 개수 중 작은 묶음의 개수가 최종 결과

메모리 : 31256KB, 시간 : 44ms

❍ CODE

s = input()
zero = 0
one = 0

# 첫 숫자를 기준으로 묶음 개수 1로 설정
if s[0] == '0':
    zero += 1
else:
    one += 1

for i in range(len(s) - 1): # 주어진 문자열 탐색 시작
    if s[i] != s[i + 1]:    # 현재 숫자와 다음 숫자가 동일하지 않다면, 묶음 종료
        if s[i + 1] == '0': # 다음 숫자가 0이라면, 0의 묶음 개수를
            zero += 1
        else:               # 그렇지 않다면, 1의 묶음 개수를 1 증가
            one += 1

print(min(zero, one))       # 0과 1의 각 묶음 개수 중 작은 묶음의 개수가 최종 결과

메모리 : 31256KB, 시간 : 40ms
 
둘의 코드 차이는 묶음이 시작될 때 카운트를 세는지, 끝날 때 세는 지의 차이일 뿐 동일하다.
아래의 코드의 경우, sys를 이용하면 틀렸습니다라고 결과가 뜨는데 원인은 모르겠다..