PS/문제풀이

백준 1439 뒤집기 Python

중규리 2024. 1. 4. 16:07

🐸 문제 정보

 

1439번: 뒤집기

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

www.acmicpc.net

 

🤖 알고리즘

그리디

 

⏱️ 풀이 시간

08.05m

 

📝 풀이

직전 문제와 같이, 간단한 그리디 문제였다.

처음에 문제 이해를 잘못해서 약간의 시간이 더 소요되었다.

 

  1. 스택을 통해 연속된 0 또는 연속된 1의 개수를 파악한다
  2. 연속된 수의 개수가 더 작은 수의 개수를 출력한다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

nums = [0, 0]
stack = []
for le in list(map(int, list(input().rstrip()))):
    if stack and stack[-1] != le:
        nums[stack[-1]] += 1
        stack = [le]
    else:
        stack.append(le)

if stack:
    nums[stack[-1]] += 1

print(min(nums))