[백준 1439번] 파이썬 - 뒤집기

백준 1439 - 뒤집기

시간 제한 2초, 메모리 제한 128MB

# 조건

• 다솜이는 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만보다 작다.

출력

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

# 접근 방법

• 연속되는 0과 1의 무리가 총 몇 번씩 등장하는지 구하고, 둘 중 작은 수를 출력하면 되는 문제이다.
  • while문을 통해 처음부터 끝까지 체크해봐도 무방하다.
• 위의 말을 조금 더 생각해보면 아래와 같은 방법들로 조금 더 짧고 편하게 구할 수 있다.
  • 바뀌는 부분마다 카운트를 해주고 2로 나눠준다.
  • 1을 공백으로 바꾸고 split()으로 나눠준 카운트와, 0을 공백으로 바꾸고 split()으로 나눠준 카운트 중 작은 걸 출력한다.
  • 01을 카운트하고, 10을 카운트하여 큰 값을 출력해준다.
    • 01을 카운트하는 하는 것은 다음 01까지 즉, 01과 01 사이의 모든 1을 0으로 변경하는 거와 동일하므로 !
    • MAX로 하는 이유는 둘 중 하나는 제일 앞을 변경하지 못하므로
    • 1100110 의 경우 01의 경우 제일 앞의 1을 변경하지 못하므로 10의 카운트로 출력한다.

query = input().rstrip()  
print(max(query.count('01'), query.count('10')))