[이것이 코딩 테스트다 with Python] Chapter 11. 그리디 - 문자열 뒤집기

< 문자열 뒤집기>

 

💬 문제 설명

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있습니다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 합니다. 

....

 

입력	출력
0001100	1

💬 입력 조건

• 첫째 줄에 0과 1로만 이루어진 문자열S가 주업집니다. S의 길이는  ( S의 길이 < 1,000,000 )

💬 출력 조건

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

---

✍ 문제요약

0과 1로만 이루어진 문자열 S가 주어지는데, 연속되는 숫자를 뒤집어서 문자열 S의 모든 값들을 동일하게 만들려고 한다. 이 때 뒤집는 횟수의 최솟값을 구해야한다.

💯 문제링크

백준1439 문제와 동일하다.

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

1439번: 뒤집기

---

✅  문제 풀이

• 첫 번째 숫자부터 서로 붙어있는 두 수가 다른지 같은지 비교한다.
• 만약에 두 수가 다르면 뒤집어서 같은 수로 바꿔 줘야한다. 
• 연속되는 수를 모두 뒤집어야 한다.
• 또한, 비교하는 두 수 중 뒤에 숫자를 뒤집어야 한다. 앞에 숫자를 뒤집으면 동작이 한번 더 발생할 수 있다.

S = list(input())

i, count = 1, 0                               # i : 확인할 위치, count : 뒤집기 횟수
while i < len(S):                             # i가 문자 범위 안에 있을 때
    if S[i] != S[i - 1]:                      # i번째 문자와 한칸 앞의 문자가 다르면
        count += 1                            # 뒤집어야한다.
        while i < len(S) and S[i] != S[i-1]:  # 연속된 숫자를 다 뒤집기위한 조건
            S[i] = S[i-1]                     # 뒤집고나서
            i += 1                            # i를 한칸씩 이동
    i += 1                                    # 뒤집기 끝나거나, 뒤집은거 없는경우 다음 번째 확인
print(count)