백준 1439번 뒤집기
뒤집기 문제 바로 가기
문제 설명
문제:
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 이 문자열을 모두 같은 숫자로 만들기 위해 연속된 숫자들을 골라 뒤집을 수 있다.
예시:
S = 0001100 → 전체 뒤집기: 1110011 → 4~5번째만 뒤집기: 1111111 (총 2회)
→ 4~5번째만 처음에 바로 뒤집기: 0000000 (총 1회)
입력:
- 문자열 S (길이 ≤ 1,000,000)
출력:
- 모든 숫자를 같게 만들기 위한 최소 뒤집기 횟수
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 이 문자열을 모두 같은 숫자로 만들기 위해 연속된 숫자들을 골라 뒤집을 수 있다.
예시:
S = 0001100 → 전체 뒤집기: 1110011 → 4~5번째만 뒤집기: 1111111 (총 2회)
→ 4~5번째만 처음에 바로 뒤집기: 0000000 (총 1회)
입력:
- 문자열 S (길이 ≤ 1,000,000)
출력:
- 모든 숫자를 같게 만들기 위한 최소 뒤집기 횟수
풀이 코드 (Python)
S = list(input())
count_0 = 0
count_1 = 0
if S[0] == '0':
count_0 += 1
else:
count_1 += 1
for i in range(len(S) - 1):
if S[i] != S[i + 1]:
if S[i + 1] == '0':
count_0 += 1
else:
count_1 += 1
print(min(count_0, count_1))
해결 전략
- 문자열을 순회하며 인접 문자가 바뀌는 순간을 기준으로 그룹을 나눈다.
- 0으로 구성된 그룹 수와 1로 구성된 그룹 수 중 더 작은 수를 뒤집는 것이 최소 횟수이다.