백준 1439번 문제 '뒤집기' C++

🔥 백준 1439번 "뒤집기" — 시뮬레이션 기반 구현 & 오류 해결 완전 분석

문자열을 실제로 조작하면서 해결하려다 보니, 단순해 보였던 문제에서 세 번이나 틀렸습니다.
이 글은 직접 문자열을 뒤집어가며 해결한 백준 1439번 문제의 풀이 과정, 겪었던 오류 3가지,
그리고 최종 정답 코드를 단계별로 설명한 글입니다.

✅ 1. 문제 설명

문제 링크: https://www.acmicpc.net/problem/1439

문자열 S는 0과 1로만 이루어져 있으며,
한 번의 연산으로 연속된 숫자 하나 이상의 구간을 선택해 모두 뒤집을 수 있습니다 (0 → 1, 1 → 0).

이런 연산을 최소한으로 사용해 문자열 전체를 전부 같은 숫자로 만드는 것이 목표입니다.

💡 2. 접근 아이디어

일반적인 해법은 “0 그룹 수, 1 그룹 수를 세고 그 중 작은 값을 출력”하는 그리디입니다.
하지만 저는 다음과 같이 접근했습니다:

• 문자열을 직접 뒤집으며 구간을 줄여나간다.
• 매 루프마다 문자열을 훑어 연속된 같은 숫자의 구간을 start~end 형태로 구분한다.
• 0과 1 구간의 개수를 센 후, 더 적은 쪽의 구간 하나만 뒤집는다.
• 문자열 전체가 같은 숫자가 될 때까지 반복.
• 바뀐 횟수를 cnt에 저장하여 출력.

❌ 3. 오류가 있었던 전체 코드

#include <iostream>
#include <cstring>
using namespace std;

struct Point {
    int start;
    int end;
    char k;
};

int main(void) {
    char arr[100];  // ❌ 입력 길이 제한
    Point arr2[100];
    int cnt = 0;
    cin >> arr;
    size_t n = strlen(arr);

    while (true) {
        int j = 0, cnt_0 = 0, cnt_1 = 0, start = 0, end = 0;

        for (int i = 0; i < n; i++) {
            if (arr[i] != arr[i + 1]) {
                end = i;
                arr2[j] = {start, end, arr[i]};
                j++;
                start = i + 1;
            }
        }

        // ❌ 오류: cnt_0, cnt_1을 세기 전에 종료 판단
        if (cnt_0 == 0 || cnt_1 == 0)
            break;

        for (int i = 0; i < j; i++) {
            if (arr2[i].k == '0') cnt_0++;
            else cnt_1++;
        }

        cnt++;

        if (cnt_1 > cnt_0) {
            for (int i = 0; i < j; i++) {
                if (arr2[i].k == '0') {
                    for (int k = arr2[i].start; k <= arr2[i].end; k++)
                        arr[k] = '1';
                    break;
                }
            }
        } else {
            for (int i = 0; i <= j; i++) {  // ❌ 오류: 인덱스 초과
                if (arr2[i].k == '1') {
                    for (int k = arr2[i].start; k <= arr2[i].end; k++)
                        arr[k] = '0';
                    break;
                }
            }
        }
    }

    cout << cnt << endl;
    return 0;
}

❗️4. 개별 오류 설명

🔴 오류 1: 입력 배열 크기 제한

char arr[100];

• 입력 문자열은 최대 1,000,000자리까지 가능.
• 이 선언은 예제는 통과하지만, 실제 채점 데이터에서 문자열 일부만 받아 틀림.

✅ 해결:

char arr[1000001];  // 넉넉하게 확보

🔴 오류 2: 구간 개수 세기 전에 종료 판단

if (cnt_0 == 0 || cnt_1 == 0)
    break;

• cnt_0, cnt_1을 아직 세지도 않았는데 종료 판단을 함
• 항상 break에 걸리거나, 무한 루프 유발 가능

✅ 해결:

// 구간 세기 먼저
for (int i = 0; i < j; i++) {
    if (arr2[i].k == '0') cnt_0++;
    else cnt_1++;
}
if (cnt_0 == 0 || cnt_1 == 0) break;

🔴 오류 3: 잘못된 반복 조건 (i <= j)

for (int i = 0; i <= j; i++)  // ❌ j는 구간 개수이므로 i == j는 초과

• arr2[j]는 아직 값이 안 들어간 영역
• 런타임 오류 가능성, 쓰레기 값 참조 위험

✅ 해결:

for (int i = 0; i < j; i++)  // ✅ 인덱스 안전

✅ 5. 해결된 전체 코드 (정답)

#include <iostream>
#include <cstring>
using namespace std;

struct Point {
    int start;
    int end;
    char k;
};

int main() {
    char arr[1000001];
    Point arr2[1000001];
    int cnt = 0;

    cin >> arr;
    size_t n = strlen(arr);

    while (true) {
        int j = 0, cnt_0 = 0, cnt_1 = 0, start = 0, end = 0;

        for (int i = 0; i < n; i++) {
            if (arr[i] != arr[i + 1]) {
                end = i;
                arr2[j++] = {start, end, arr[i]};
                start = i + 1;
            }
        }

        for (int i = 0; i < j; i++) {
            if (arr2[i].k == '0') cnt_0++;
            else cnt_1++;
        }

        if (cnt_0 == 0 || cnt_1 == 0) break;

        cnt++;

        if (cnt_1 > cnt_0) {
            for (int i = 0; i < j; i++) {
                if (arr2[i].k == '0') {
                    for (int k = arr2[i].start; k <= arr2[i].end; k++)
                        arr[k] = '1';
                    break;
                }
            }
        } else {
            for (int i = 0; i < j; i++) {
                if (arr2[i].k == '1') {
                    for (int k = arr2[i].start; k <= arr2[i].end; k++)
                        arr[k] = '0';
                    break;
                }
            }
        }
    }

    cout << cnt << '\n';
    return 0;
}

🧩 6. 해결 코드 분해 및 개별 설명

✅ 입력 문자열 및 구간 저장용 구조체 배열

char arr[1000001];
Point arr2[1000001];

• 입력 문자열 arr는 최대 100만까지 받을 수 있도록 설정
• arr2는 구조체 배열로, 구간을 {start, end, 문자} 형태로 저장

✅ 구간 나누기

for (int i = 0; i < n; i++) {
    if (arr[i] != arr[i + 1]) {
        end = i;
        arr2[j++] = {start, end, arr[i]};
        start = i + 1;
    }
}

• 문자열을 순회하며 같은 문자가 끊기는 위치에서 구간을 분리
• 각 구간은 구조체로 저장

✅ 구간 수 세기

for (int i = 0; i < j; i++) {
    if (arr2[i].k == '0') cnt_0++;
    else cnt_1++;
}

• 각 구간의 문자가 0인지 1인지 확인하여 개수 저장

✅ 종료 조건

if (cnt_0 == 0 || cnt_1 == 0) break;

• 둘 중 하나만 존재한다면 이미 문자열이 완전히 같음 → 종료

✅ 더 적은 쪽 구간 하나만 뒤집기

if (cnt_1 > cnt_0) {
    for (int i = 0; i < j; i++) {
        if (arr2[i].k == '0') {
            for (int k = arr2[i].start; k <= arr2[i].end; k++)
                arr[k] = '1';
            break;
        }
    }
}
else {
    for (int i = 0; i < j; i++) {
        if (arr2[i].k == '1') {
            for (int k = arr2[i].start; k <= arr2[i].end; k++)
                arr[k] = '0';
            break;
        }
    }
}

✅ 결과 출력

cout << cnt << '\n';

• 반복한 횟수(cnt)를 정답으로 출력

✅ 7. 마무리

이 문제는 표면적으로는 간단해 보이지만,
직접 구현해보면 배열 크기 관리, 루프 조건 순서, 인덱스 처리에서 많은 실수가 발생합니다.

특히 “문자열을 직접 바꾸면서 확인하는 구현력”은
실제 알고리즘 문제에서 오류를 추적하는 능력을 크게 키울 수 있습니다.

단순히 "그룹 수만 세서 푸는 정답"이 아니라,
시뮬레이션 기반으로 완전히 구현한 방식을 통해 한 단계 더 깊이 이해할 수 있는 기회가 되었습니다.