[그리디 알고리즘 Lv.03] 1439번 뒤집기 (Python)

 

1. 문제

    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가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

 

 

2. 문제 포인트

• 0과 1로 이루어진 문자열 입력
• 모두 같은 숫자로 만들기 (0, 1 무관)
• 한번에 근접한 문자 같이 뒤집기 가능

 

반응형

 

3. 접근법

• 모든 숫자를 0으로 만들때와 1로 만들때를 구한 후 작은 값 출력
• 전체를 1을 만드는 뒤집기 횟수 ==  split("0")으로 리스트를 생성한 후 만든 요소의 개수
• 전체를 0을 만드는 뒤집기 횟수 ==  split("1")으로 리스트를 생성한 후 만든 요소의 개수
• min()으로 두가지 경우 중 작은 값 출력

 

 

4. 결과 코드

import sys

a = sys.stdin.readline().strip()

# 1, 0을 기준으로 문자열을 나눠 리스트 만들기
## list comprehension을 이용하여 내용없는 요소는 제거
b = [bb for bb in a.split("1") if bb]
c = [cc for cc in a.split("0") if cc]

print(min(len(b), len(c)))

# 1439번 뒤집기
# https://www.acmicpc.net/problem/1439