백준 1439번 "뒤집기" — 파이썬으로 푸는 2가지 방법

🔥 백준 1439번 "뒤집기" — 파이썬으로 푸는 2가지 방법

뒤집기 연산을 최소 몇 번 해야 문자열이 전부 같은 숫자가 될까?
이 문제는 문자열을 직접 조작해볼 수도 있고, 핵심 패턴만 파악해서 풀 수도 있습니다.
이번 글에서는 Python으로 해결하는 두 가지 풀이 방식을 소개하고, 어떤 방법이 더 효율적인지도 비교합니다.

📘 문제 요약

• 문자열 S는 0과 1로만 구성되어 있음
• 연속된 숫자들을 한 번에 골라 뒤집을 수 있음
• 전체 문자열을 하나의 숫자(0 또는 1)로 만들기 위해 필요한 최소 뒤집기 횟수를 구하라

💡 핵심 아이디어

"문자열 전체를 같은 숫자로 만들기 위해 뒤집어야 하는 구간 수가 핵심이다."

즉,

• 0이 한 덩어리로 몇 번 나오는지
• 1이 한 덩어리로 몇 번 나오는지

이 두 값을 비교해서 더 적은 쪽만 전부 뒤집으면 된다.

🔄 방법 1: 시뮬레이션 기반 구현

직접 문자열을 리스트로 바꾸고, 실제로 하나씩 뒤집는 방식입니다.
구간을 저장하고, 적은 쪽의 그룹 중 하나를 찾아 직접 수정합니다.

def main():
    arr = list(input().strip())
    cnt = 0
    n = len(arr)

    while True:
        arr2 = []
        cnt_0 = 0
        cnt_1 = 0
        start = 0
        end = 0

        for i in range(n):
            if i == n - 1 or arr[i] != arr[i + 1]:
                end = i
                arr2.append((start, end, arr[i]))
                start = i + 1

        for s, e, k in arr2:
            if k == '0':
                cnt_0 += 1
            else:
                cnt_1 += 1

        if cnt_0 == 0 or cnt_1 == 0:
            break

        cnt += 1

        if cnt_1 > cnt_0:
            for s, e, k in arr2:
                if k == '0':
                    for i in range(s, e + 1):
                        arr[i] = '1'
                    break
        else:
            for s, e, k in arr2:
                if k == '1':
                    for i in range(s, e + 1):
                        arr[i] = '0'
                    break

    print(cnt)

main()

✅ 특징

• 그룹을 하나하나 분해하고 수정하는 방식
• 문자열이 어떻게 바뀌는지 직접 확인 가능
• 반복문 + 리스트 수정 구조라서 구현 훈련에 좋음
• 단점: 코드가 길고 비효율적

⚡ 방법 2: 그룹 수만 세는 최적화 코드

문자열을 직접 뒤집지 않고,
'이전 문자와 다를 때'마다 그룹이 바뀌었다고 판단해서 단순히 카운팅만 합니다.

n = input()

cnt0 = 0
cnt1 = 0

# 첫 문자에 따라 초기 그룹 등록
if n[0] == '0':
    cnt0 += 1
else:
    cnt1 += 1

# 문자 바뀔 때마다 그룹 수 증가
for i in range(1, len(n)):
    if n[i] != n[i - 1]:
        if n[i] == '0':
            cnt0 += 1
        else:
            cnt1 += 1

print(min(cnt0, cnt1))

✅ 특징

• 문자 하나씩 보면서 그룹 수만 세면 됨
• 문자열 직접 수정 필요 없음
• 시간복잡도 O(N), 공간복잡도 O(1)
• 가장 빠르고 짧은 풀이

🔍 두 방식 비교 요약

항목	시뮬레이션 방식	그룹 수 계산 방식
핵심 아이디어	직접 뒤집기 시도	구간 수만 계산
구현 난이도	복잡함	간단함
코드 길이	김	짧음
학습 포인트	문자열 수정 연습	패턴 분석과 카운팅
성능	느림 (리스트 반복 수정)	빠름 (한 번 순회)

✅ 마무리 요약

• 이 문제는 문자열을 직접 뒤집지 않아도 충분히 풀 수 있다.
• "0 그룹이 몇 개인가 vs 1 그룹이 몇 개인가" → 더 적은 쪽만 뒤집으면 됨
• 학습용으로는 시뮬레이션 방식도 한 번쯤 직접 구현해볼 만하다.
• 실전에서는 그룹 수 계산 방식이 가장 효율적이다.