백준 1439번 '뒤집기' C++ 개선

2025.06.18 - [백준 스터디] - 백준 1439번 문제 '뒤집기' C++

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

이전에 했던 내용의 개선

 

 

🔥 백준 1439번 "뒤집기"

문자열을 조작할 수 있는 가장 기본적인 C언어 수준 기능만으로
백준 1439번 '뒤집기' 문제를 정확하고 효율적으로 푸는 법을 정리합니다.
구조체 없이, STL 없이, string 없이 오직 char 배열 + for문만으로 정답을 구해봅니다.

📘 문제 설명

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

문자열 S가 주어진다. S는 0과 1로만 이루어져 있다.
연속된 숫자 하나 이상의 구간을 골라 전부 뒤집는 연산을 반복하여,
문자열 전체를 전부 같은 숫자로 만들고자 한다.
이때 최소 연산 횟수를 출력하라.

🔸 예시 입력 1

0001100

🔸 예시 출력 1

1

💡 아이디어: 그룹 개수만 세면 된다

문자열을 통째로 뒤집지 않아도 됩니다.
0 그룹이 몇 개인지, 1 그룹이 몇 개인지만 세면 그 중 더 적은 쪽을 전부 뒤집으면 문자열 전체가 같아집니다.

예: 0001100

• 0 그룹: 000, 00 → 2개
• 1 그룹: 11 → 1개

→ 더 적은 1 그룹만 뒤집으면 됩니다.
→ 정답은 1

🔧 구현 조건

• 구조체 ❌
• STL (string, vector 등) ❌
• 직접 문자열을 뒤집는 시뮬레이션 ❌
• 오직 char 배열 + 반복문만 사용 ✅
• 시간복잡도 O(N), 공간복잡도 O(1) ✅

✅ 정답 코드 (STL, 구조체 없이)

#include <iostream>
using namespace std;

int main() {
    char arr[1000001];
    cin >> arr;

    int cnt0 = 0, cnt1 = 0;

    // 첫 문자의 그룹 수 초기화
    if (arr[0] == '0') cnt0++;
    else cnt1++;

    for (int i = 1; arr[i] != '\0'; i++) {
        if (arr[i] != arr[i - 1]) {
            if (arr[i] == '0') cnt0++;
            else cnt1++;
        }
    }

    // 더 적은 그룹 수가 최소 뒤집기 횟수
    cout << (cnt0 < cnt1 ? cnt0 : cnt1) << '\n';
    return 0;
}

🧩 코드 설명

1. 입력 받기

char arr[1000001];
cin >> arr;

• 최대 입력 길이가 1,000,000이므로 넉넉하게 배열 선언

2. 첫 문자에 따라 초기 그룹 하나 등록

if (arr[0] == '0') cnt0++;
else cnt1++;

• 처음 시작하는 그룹은 무조건 1개

3. 그룹 수 세기

for (int i = 1; arr[i] != '\0'; i++) {
    if (arr[i] != arr[i - 1]) {
        if (arr[i] == '0') cnt0++;
        else cnt1++;
    }
}

• 현재 문자와 이전 문자가 다르면 새로운 그룹이 시작된 것
• 해당 문자의 종류에 따라 카운팅

4. 정답 출력

cout << (cnt0 < cnt1 ? cnt0 : cnt1) << '\n';

• 0 그룹과 1 그룹 중 더 적은 그룹만 뒤집으면 전체 통일 가능
• 따라서 그 중 작은 값을 출력

🧪 예시 테스트

입력

11001100110011000001

출력

4

• 0 그룹: 4개
• 1 그룹: 5개
• 최소값: 4

✅ 마무리 정리

항목	내용
시간 복잡도	O(N)
공간 복잡도	O(1)
사용 도구	char 배열, for문