[그리디] 백준 1439번 뒤집기 Python 풀이

문제 요약

0과 1로만 이루어져 있는 문자열 S의 모든 숫자를 같도록 만들어야 한다. 연속된 하나 이상의 숫자를 잡고 뒤집는 것으로 숫자를 바꾸며, 수를 뒤집는 행동을 최소한으로 하는 횟수를 출력하라.

※ 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미

백준 1439번 문제 바로가기

입력

첫 번째 줄에 문자열 S 입력

S의 길이 < 100만

출력

첫째 줄에 뒤집기 최소 횟수 출력

입출력 예시

입력	출력
0001100	1

코드

정답 예시 1

약 30분 소요

 

S = input()
cntZero = cntOne = 0
numOne = S.split("0")
numZero = S.split("1")

for i in numOne:
    if i != "":
        cntOne += 1
for i in numZero:
    if i != "":
        cntZero += 1
if cntOne > cntZero:
    print(cntZero)
else:
    print(cntOne)

 

"0", "1" 기준으로 split하면 공백도 함께 들어감. 그래서 공백이 아닐 경우의 수를 count

정답 예시 2

약 30분 소요

PyPy3이 보통 속도가 빠르다고 해서 사용했는데 메모리도 많이 쓰고 속도도 느리네.

앞으로는 비교하면서 사용해봐야겠다.

S = input()
numOne = S.split("0")
numZero = S.split("1")

cntOne = len(numOne) - numOne.count("")
cntZero = len(numZero) - numZero.count("")

if cntOne > cntZero:
    print(cntZero)
else:
    print(cntOne)

""를 찾아서 삭제하면 len(numOne)로 개수를 셀 수 있었을텐데 문법을 몰라서 저렇게 계산

.count("1")로 하지 않은 이유는 .split("0") 하면 ["", "1", "111", "11"] 이런 식으로 나올 수 있기 때문

피드백

문법이 부족하다는 생각을 했지만 일단 몰라도 문제를 풀도록 하기 위해서 검색 없이 문제를 풀었다.

 

내가 찾은 패턴

• 현재 숫자와 다음 숫자가 다를 경우, count
• 0을 뒤집는 횟수와 1을 뒤집는 횟수를 비교하여 작은 수 출력

다른 사람 풀이 참고

참고 블로그 alpyrithm_알파이리즘

• 반복되는 0, 1을 빼고 change[]에 저장한 후 계산
• 더 작은 수를 골라낼 때는 min()

[알고리즘][Python] 백준(BOJ) 1439 뒤집기_파이썬