백준 1439번 "뒤집기" - 오답 노트

오늘의 주인공은 백준 1439번 "뒤집기" 문제다. 처음에는 간단해 보였지만 생각지 못한 예외 케이스에 계속 실패했다.

TIP: 연속된 숫자들의 그룹을 세는 문제에서는 첫 요소도 하나의 그룹으로 세어야 한다!

문제 요약

문제는 꽤 단순했다.
1. 0과 1로만 이루어진 문자열 S가 주어짐
2. 연속된 하나 이상의 숫자를 뒤집을 수 있음 (0→1, 1→0)
3. 문자열을 모두 0 또는 모두 1로 만드는 최소 횟수를 구해야 함

예를 들어, 0001100의 경우

• 모두 0으로 만드려면: 1이 나타나는 연속된 구간을 한 번 뒤집으면 됨 → 1회
• 모두 1로 만드려면: 0이 나타나는 두 구간을 각각 뒤집어야 함 → 2회

따라서 답은 1이 된다.

첫 번째 시도

처음에는 문자열을 순회하면서 연속된 같은 숫자 그룹을 세는 방식으로 접근했다. 하지만 코드가 계속 틀렸고, 뭐가 문제인지 한참 고민했다.

import sys
input = sys.stdin.readline
string = input().strip()

def find_count_to_turn_out_to_all_zero_or_all_one(string):
    # 모든 문자열 내 숫자가 같으면 0번 뒤집는다.
    result = "".join(set(string))
    if(len(result) == 1):
        return 0
    
    count_all_zero = 0
    count_all_one = 0
    
    # 이 부분이 없었음! 첫 번째 문자 처리를 빼먹었다.
    
    for i in range(len(string)-1):
        if(string[i] != string[i+1]):
            if(string[i+1] == "0"):
                count_all_one += 1
            if(string[i+1] =="1"):
                count_all_zero += 1
    return min(count_all_zero , count_all_one)

문제 분석: 첫 번째 문자도 하나의 그룹

자, 위 코드의 문제를 찾아보자!

문제는 첫 번째 문자를 처리하지 않았다는 점이다. 예를 들어 1100이라는 문자열이 있을 때

• 첫 번째 '1'은 '모두 0으로 만들기' 위해서 반드시 뒤집어야 할 그룹
• 하지만 내 코드에서는 이 첫 번째 그룹을 세지 않았다!

해결책: 첫 번째 문자도 고려하기

첫 번째 문자를 처리하는 코드를 추가했다.

# 첫 번째 문자의 그룹 처리
if(string[0] == "0"):
    count_all_one +=1
elif(string[0] == "1"):
    count_all_zero += 1

왜 이렇게 처리할까?

• 첫 번째 문자가 '0'이면 → 모두 '1'로 만들려면 이 그룹을 뒤집어야 함
• 첫 번째 문자가 '1'이면 → 모두 '0'으로 만들려면 이 그룹을 뒤집어야 함

완성된 코드

전체 코드는 다음과 같다.

import sys
input = sys.stdin.readline
string = input().strip()
def find_count_to_turn_out_to_all_zero_or_all_one(string):
    #모든 문자열 내 숫자가 같으면 0번 뒤집는다.
    result = "".join(set(string))
    if(len(result) == 1):
        return 0
    
    count_all_zero = 0
    count_all_one = 0
    if(string[0] == "0"):
        count_all_one +=1
    elif(string[0] == "1"):
        count_all_zero += 1
    for i in range(len(string)-1):
        if(string[i] != string[i+1]):
            if(string[i+1] == "0"):
                count_all_one += 1
            if(string[i+1] =="1"):
                count_all_zero += 1
    return min(count_all_zero , count_all_one)
# 실행
result = find_count_to_turn_out_to_all_zero_or_all_one(string)
print(result)

코드 분석 및 설명

이 코드 동작 로직을 정리하면 다음과 같이 작동한다.

1. 먼저 문자열에 0과 1이 모두 있는지 확인 (len(set(string)) == 1이면 이미 모두 같음)
2. 첫 번째 문자부터 시작하는 연속된 그룹을 카운트
3. 문자열 전체를 순회하며 문자가 바뀌는 지점마다:
   • 다음 문자가 '0'이면 → '1'로 만들기 위한 뒤집기 횟수 증가
   • 다음 문자가 '1'이면 → '0'로 만들기 위한 뒤집기 횟수 증가
4. 두 경우(모두 0 또는 모두 1) 중 최소값 반환

결론: 사소한 조건도 중요하다!

이 문제를 통해 배운 점

1. 첫 번째 요소도 그룹으로 처리해야 하는 경우가 많다! 이런 엣지 케이스를 항상 생각하자.
2. 0과 1을 뒤집는 최소 횟수는 '연속된 같은 숫자의 그룹 수'와 관련이 있다.
3. 최종 결과를 결정할 때는 '모두 0으로' 또는 '모두 1로' 두 가지 경우 중 더 작은 값을 선택하는 것이 중요하다.

문제의 핵심은 "연속된 같은 숫자들의 그룹이 몇 개나 있는지" 파악하는 것이었다. 그리고 첫 번째 그룹(첫 번째 문자부터 시작)도 반드시 세어야 한다는 점!

결국 사소한 디테일이 문제 해결의 성패를 가르는 경우가 많다는 것을 다시 한번 깨달았다 ㅠㅠ 다음에는 더 꼼꼼하게 접근해야겠다.