[Greedy] 이코테 “문자열 뒤집기” Python 풀이

문제

• 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있습니다.
• 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 합니다.
• 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것입니다.
• 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미합니다.
• 예를 들어 S = 0001100일 때는 다음과 같습니다.
  • 전체를 뒤집으면 1110011이 됩니다.
  • 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 두 번 만에 모두 같은 숫자로 만들 수 있습니다.
• 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있습니다.
• 문자열 S가 주어졌을 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력하세요.

입력 조건

• 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어집니다. S의 길이는 100만보다 작습니다.

출력 조건

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

입력 예시

0001100

출력 예시

1

풀이

• 문제에서 헷갈릴 수 있는 부분을 한 번 더 짚고 넘어가겠습니다.
  • 0001100을 1111111로 만들기 위해선,
  • 0001100 → 1111100 → 1111111 로,
  • 총 2번 과정이 필요합니다.
• 전체 문자열을 처음부터 탐색하며,
• 0이 연속되는 부분의 개수와 1이 연속되는 부분의 개수를 파악한 뒤,
• 더 적은 개수를 가진 값을 출력하면 됩니다.
• 연속되는 부분의 개수는, 현재 숫자와 다음 숫자가 달라질 때, 카운팅하면 됩니다.

예제 코드

import sys

# 문자열 입력
s = list(sys.stdin.readline().rstrip())

# 0이 연속된 부분
count0 = 0
# 1이 연속된 부분
count1 = 0

# 첫 번째 정수는 곧바로 연속된 부분으로 추가
if (s[0] == '0'):
    count0 += 1
else:
    count1 += 1

# 정수를 순서대로 탐색하며, 연속된 정수가 다른 정수로 바뀔 때, 연속된 부분의 개수 추가
for i in range(len(s)-1): 
    # 연속된 정수가 다음 수에서 다른 정수로 바뀔 때
    if (s[i] != s[i+1]):
        # 다음 수에서 0으로 바뀌는 경우
        if (s[i+1] == '0'):
            count0 += 1
        # 다음 수에서 1로 바뀌는 경우
        else:
            count1 += 1

# 연속된 부분의 개수가 적은 값을 출력
print(min(count0, count1))

참고

• 이것이 취업을 위한 코딩 테스트다. with python