[그리디 Greedy] 03. 문자열 뒤집기 / 백준 1439번 / 파이썬

그리디 (Greedy)

현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘

 

---

문자열 뒤집기

난이도 ★☆☆  풀이시간 20분  시간제한 2초

 

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있습니다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만드려고 합니다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것입니다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미합니다.

예를 들어 S = 0001100일 때는 다음과 같습니다.

• 전체를 뒤집으면 1110011이 됩니다.
• 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 두 번 만에 모두 같은 숫자로 만들 수 있습니다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있습니다.

문자열 S가 주어졌을 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력하세요.

 

입력 조건

• 첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

출력 조건

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

입력 예시

0001100

출력 예시

1

---

코드

# 입력받은 문자열 (0과 1로만 이루어짐)
s = input()
# 현재 저장된 숫자(0 혹은 1) : 문자열의 첫번째 원소로 초기화
now = int(s[0])
# 0과 1의 덩어리 개수를 저장할 리스트 : result[0]에는 0의 덩어리 개수, result[1]에는 1의 덩어리 개수
result = [0] * 2
# 첫번째 원소에 해당하는 숫자의 개수 1로 초기화
result[now] = 1

for i in s:
    # 현재 저장된 숫자와 다음 숫자가 같다면, 같은 덩어리 이므로 다음 반복문으로 넘어감
    num = int(i)
    if now == num:
        continue
    # 다르면 다른 덩어리이므로 덩어리 개수 증가시키고 현재 숫자 갱신
    else:
        result[num] += 1
        now = num

print(min(result[0], result[1]))

 

---

참고

2021.07.13 - [자료구조 알고리즘] - [알고리즘] Greedy Algorithm 탐욕 알고리즘 / 파이썬

[알고리즘] Greedy Algorithm 탐욕 알고리즘 / 파이썬

 

출처

나동빈, 『이것이 취업을 위한 코딩테스트다 with 파이썬』, 한빛미디어(주), 2020년

 

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

1439번: 뒤집기