[Python] 백준 - 1439 뒤집기

 

  문제

https://www.acmicpc.net/problem/1439

 

🔹 문제

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

🔹 출력

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

 

입력	출력
11101101	2

 

  풀이 방법

 

🔹 그리디 알고리즘

🔹 연속된 0 또는 1을 하나의 묶음이라 보고, 묶음의 수가 더 적은 것을 뒤집으면 된다. 즉, 묶음의 수가 더 적은 쪽의 값을 출력한다.

🔹 연속된 0 또는 1의 묶음을 찾기 위해 split를 사용했기 때문에 각 덩어리만 남기기 위해 list comprehension을 사용했다.

🔹 숏코딩을 보니, '01'인 경우와 '10'인 경우를 각각 count하고 1을 더한 뒤 2로 나누는 방식으로 해결했다.

 

 

  구현 코드

import sys
s = sys.stdin.readline().strip()
s_0 = [x for x in s.split('0') if x!='']
s_1 = [x for x in s.split('1') if x!='']
print(min(len(s_0),len(s_1)))

 

  실행 결과

 

  💡