[백준] 1439 뒤집기 (Python 파이썬)

www.acmicpc.net/problem/1439

1439번: 뒤집기

문제 설명

0과 1로만 이루어진 문자열 S이 주어진다. 이 문자열S을 모두 같은 숫자로 이루어진 문자열로 바꾸려고 하는데,

연속된 하나 이상의 숫자를 뒤집을 수 있다. (0을 1로, 1을 0로)

 

예를 들어, 1001001이 있으면 1001001 -> 1111001 -> 1111111 과 같이 바꿀 수 있다.

주어진 문자열을 바꾸는데 필요한 최소 횟수를 출력하면 된다.

---

풀이 과정

문제를 보고, 가장 먼저 떠올랐던 풀이법은,

for문을 처음부터 문자열의 끝까지 모두 돌면서 숫자가 바뀌는 순간을 카운트하여

1이 0으로 바뀌는 순간과 0이 1로 바뀌는 순간중 더 작은 값을 출력하도록 하는 방법이다.

 

하지만, 문제에서 S의 길이는 100만보다 작다고 했으므로, 하나하나 비교하기에는 시간초과가 발생할 것 같다는 생각이 들었다. (하지만 의외로, 이 방법도 시간초과가 발생하지는 않았다.)

 

그래서 파이썬의 split을 이용하여 split(1)과 split(0)을 하여 더 작은값을 출력하도록 하는 방법을 사용하였다.

1001001을 0으로 구분하면 [ '1', '', '1', '', '1' ] 이고, 1로 구분하면 [ '', '00', '00', '' ] 이다.

즉, 뒤집었을 때 원본이 살아있는 부분만 수가 나타나고 나머지는 ''로 나타나므로 다음과 같이 적용할 수 있다.

import sys
a = sys.stdin.readline().rstrip()

b = a.split("0")
c = a.split("1")

b2 = b.count('')
c2 = c.count('')

print(min(len(b)-b2, len(c)-c2))

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !