백준 1439: 뒤집기

[Silver V] 뒤집기 - 1439

문제 링크

성능 요약

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

분류

그리디 알고리즘(greedy), 문자열(string)

문제 설명

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

예를 들어 S=0001100 일 때,

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

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

입력

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

출력

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

---

문제 풀이

아이디어

반복문을 돌면서 다음 값이 현재 값과 동일하면 넘어가고, 바뀔 때 0이냐 1이냐에 따라 값을 증가시키자.

처음에는 그냥 0의 개수와 1의 개수를 Counter 메서드를 사용하여 판단하고, 이중에서 적은 애를 찾아 반복문을 돌 때 해당 값이 아니고, 다음 값과 현재 값이 다를 때 더하려고 했었다.

하지만 이러니까, 예제 입력 4인 11001100110011000001에서 수가 많은 0을 뒤집는게 더 적게 뒤집는데, 내 코드대로면 무조건 1을 뒤집게 되어 값이 틀리게 나왔다.

그래서 그냥 0을 뒤집었을 때, 1을 뒤집었을 때의 값을 각각 계산하고, 마지막에 둘 중 최소값을 구하였더니 정답이 되었다.

코드

import sys

s = list(sys.stdin.readline().rstrip())
s = list(map(int, s))  # 문자열 '0' -> 0으로, '1'을 1로 변환

zero_result = 0  # 0을 뒤집었을 경우
one_result = 0  # 1을 뒤집었을 경우

for i in range(len(s) - 1):
  if s[i] == 1:  # 뒤집어야 하는게 1인 경우
    if s[i + 1] != 1:  # 현재 값은 1이 아니다. -> 연속적인게 끝났다. -> 값을 증가
      one_result += 1
  else:  # 뒤집어야 하는게 0인 경우
    if s[i + 1] != 0:
      zero_result += 1

# 마지막 문자 계산
if s[-1] == 0: 
  zero_result += 1
else:
  one_result += 1

# 0을 뒤집었을 때, 1을 뒤집었을 때 중에서 최소값을 출력
print(min(one_result, zero_result))

여기서 나는 반복문을 마지막 이전까지만 돌았기 때문에 ( 인덱스 범위 초과 고려 ) 마지막 문자 계산은 따로 빼주었다.