문자열 뒤집기 최소 횟수 문제는 처음 보면 그리디처럼 보입니다. 하지만 실제 핵심은 “지금 어디를 뒤집을까”가 아니라, 문자 하나가 아니라 연속된 그룹을 봐야 한다는 사실을 알아차리는 데 있습니다.
결론부터 말하면 답은 min(0 그룹 수, 1 그룹 수)입니다. 이번 글에서는 왜 이 식이 정확한지, 그리고 왜 이 문제가 그리디 느낌은 나지만 본질은 관찰형 애드혹 문제인지 차근차근 설명해보겠습니다.
문제 조건
0과 1로만 이루어진 문자열이 있습니다. 여기서 같은 숫자가 연속된 구간 하나를 골라, 그 구간 전체를 뒤집을 수 있습니다. 목표는 문자열 전체를 전부 0으로 만들거나, 전부 1로 만드는 것입니다. 이때 필요한 최소 뒤집기 횟수를 구하면 됩니다.
대표 예시는 0001100입니다. 이 문자열을 보면 많은 사람이 먼저 0의 개수와 1의 개수를 세지만, 이 문제는 그 방향으로 들어가면 설명이 자주 꼬입니다.
개수보다 그룹
이 문제의 연산은 문자 하나를 뒤집는 연산이 아닙니다. 연속된 덩어리 하나를 한 번에 뒤집는 연산입니다. 이 차이가 아주 중요합니다.
예를 들어 111은 1이 세 개지만, 이 문제에서 111은 세 번 처리하는 대상이 아닙니다. 한 번에 뒤집을 수 있는 1개의 그룹입니다.
- 문자 개수보다 그룹 개수가 중요합니다.
- 원소보다 덩어리가 중요합니다.
- 최소 횟수는 그룹 수와 직접 연결됩니다.
이렇게 관점을 바꾸면 문제가 훨씬 단순해집니다.
핵심 관찰
문자열을 왼쪽부터 읽으면서 값이 바뀌는 지점을 보면, 문자열이 몇 개의 그룹으로 나뉘는지 알 수 있습니다. 예를 들어 0001100은 000, 11, 00으로 나뉩니다.
- 0 그룹: 2개
- 1 그룹: 1개
이제 바로 계산할 수 있습니다. 모두 0으로 만들고 싶다면 1 그룹들만 뒤집으면 되고, 모두 1로 만들고 싶다면 0 그룹들만 뒤집으면 됩니다. 따라서 정답은 자연스럽게 두 그룹 수 중 작은 값이 됩니다.
정답이 되는 이유
가능성
모두 0으로 만들고 싶다면 1 그룹을 전부 뒤집으면 됩니다. 각 1 그룹은 한 번의 연산으로 처리할 수 있으므로, 1 그룹 수만큼 연산하면 반드시 전체를 0으로 만들 수 있습니다. 모두 1로 만드는 경우도 완전히 같은 논리입니다.
최소성
서로 떨어져 있는 두 그룹을 한 번에 없앨 수 없기 때문입니다. 예를 들어 00110011의 1 그룹은 두 개입니다. 사이에 0이 끼어 있으므로, 이 둘을 한 번의 연산으로 동시에 처리할 수는 없습니다.
결국 모두 0으로 만들려면 각 1 그룹을 적어도 한 번씩은 처리해야 합니다. 그래서 모두 0으로 만드는 최소 횟수는 정확히 1 그룹 수입니다. 모두 1로 만드는 최소 횟수도 정확히 0 그룹 수입니다.
즉 이 값은 어림짐작이 아니라, 실제로 가능하면서 동시에 더 줄일 수 없는 정확한 최소값입니다.
예시 풀이
0001100
먼저 그룹으로 나누면 000 | 11 | 00입니다. 따라서 0 그룹은 2개, 1 그룹은 1개입니다.
전부 0으로 만들기
1단계: 000 [11] 00
뒤집은 뒤: 0000000
총 1번입니다.
전부 1로 만들기
1단계: [000] 11 00 → 1111100
2단계: 11111 [00] → 1111111
총 2번입니다.
따라서 정답은 min(2, 1) = 1입니다.
010101
그룹은 0 | 1 | 0 | 1 | 0 | 1입니다. 0 그룹 3개, 1 그룹 3개이므로 어느 쪽으로 맞춰도 3번이 필요합니다. 정답은 3입니다.
11111
그룹은 11111 하나뿐입니다. 0 그룹은 0개, 1 그룹은 1개입니다. 이미 모두 1이므로 정답은 min(0, 1) = 0입니다.
001100011
그룹은 00 | 11 | 000 | 11입니다. 0 그룹 2개, 1 그룹 2개이므로 전부 0으로 만들든 전부 1로 만들든 2번이 필요합니다. 정답은 2입니다.
그리디처럼 보이는 이유
많은 풀이가 이 문제를 그리디로 분류합니다. 완전히 틀렸다고 보기는 어렵습니다. 마지막에 두 값 중 작은 쪽을 고르기 때문입니다.
하지만 문제를 푸는 진짜 핵심은 현재 최선의 선택을 반복하는 것이 아닙니다. 먼저 전부 0으로 만들면 1 그룹 수만큼 필요하고, 전부 1로 만들면 0 그룹 수만큼 필요하다는 구조를 발견해야 합니다.
즉 핵심은 선택 전략보다 구조 관찰입니다. 그래서 이 문제는 그리디처럼 답을 고르는 순간이 있더라도, 본질적으로는 구간 관찰형 애드혹 문제라고 보는 편이 더 정확합니다.
구현 포인트
문자열을 왼쪽부터 보면서 직전 문자와 현재 문자가 다를 때마다 새 그룹이 시작됐다고 판단하면 됩니다.
- 현재 문자가 0이면 zero_groups를 1 증가
- 현재 문자가 1이면 one_groups를 1 증가
- 마지막에 min(zero_groups, one_groups)를 반환
시간 복잡도는 O(N)이고, 추가 메모리는 거의 들지 않습니다.
Python 코드
def min_flip_count(s: str) -> int:
zero_groups = 0
one_groups = 0
prev = ''
for ch in s:
if ch != prev:
if ch == '0':
zero_groups += 1
else:
one_groups += 1
prev = ch
return min(zero_groups, one_groups)
print(min_flip_count("0001100")) # 1
print(min_flip_count("010101")) # 3
print(min_flip_count("11111")) # 0이 코드가 세는 것은 문자 개수가 아니라 새로운 그룹이 시작된 횟수입니다. 이 해석만 정확하면 구현은 매우 단순합니다.
자주 하는 실수
개수 비교
가장 흔한 실수입니다. 이 문제는 몇 개가 많은지가 아니라, 몇 개의 덩어리로 나뉘어 있는지가 중요합니다.
전환 횟수
값이 바뀐 횟수는 힌트가 되지만, 그 자체가 바로 정답은 아닙니다. 결국 0 그룹이 몇 개이고 1 그룹이 몇 개인지까지 연결해야 합니다.
예외 처리
0000, 1111 같은 경우는 답이 0이어야 합니다. 그룹 수 관점으로 보면 이 예외는 따로 외울 필요도 없이 자동으로 처리됩니다.
이 문제에서 남는 감각
이 문제는 단순히 공식을 외우고 끝내기에는 아까운 문제입니다. 더 중요한 것은 이런 질문을 습관처럼 던지는 것입니다.
이 문제는 개수 문제인가, 아니면 구간 문제인가?
문자열, 배열, 압축, 색칠, 구간 병합 같은 문제에서는 원소 하나하나보다 연속된 덩어리를 보는 순간 훨씬 쉬워지는 경우가 많습니다. 이 문자열 뒤집기 문제는 그 감각을 익히기에 정말 좋은 대표 예시입니다.
정리
문자열 뒤집기 최소 횟수 문제의 답이 min(0 그룹 수, 1 그룹 수)인 이유는 분명합니다. 모두 0으로 만들려면 1 그룹들을 뒤집어야 하고, 모두 1로 만들려면 0 그룹들을 뒤집어야 하며, 떨어져 있는 그룹은 한 번에 같이 처리할 수 없기 때문입니다.
즉 이 문제는 겉으로는 그리디처럼 보여도, 실제로는 연속 구간을 읽어내는 관찰이 먼저인 문제입니다. 관련 글로는 애드혹 알고리즘 접근법: 그리디와 완전탐색 판단 기준, 애드혹 알고리즘 반례 찾는 법, 시뮬레이션 문제 풀이법: 상태 정의와 구현 순서를 함께 읽어보면 감각이 더 잘 이어집니다.
문제 원형은 백준 1439 뒤집기에서 직접 확인할 수 있습니다.
