C++로 배열에서 선행 0 제거하기

배열이 주어졌을 때, 해당 배열에서 선행 0(leading zero)을 모두 제거하고 그 결과 배열을 출력하는 것이 이번 글의 목표입니다.

입력 : arr[] = {0, 0, 0, 1, 2, 3}
출력 : 1 2 3

입력 : arr[] = {0, 0, 0, 1, 0, 2, 3}
출력 : 1 0 2 3

위 예시에서 확인할 수 있듯이, 맨 앞에 연속해서 나오는 0만 제거되고 중간에 위치한 0은 그대로 유지됩니다. 이 문제는 기존 배열에서 선행 0이 포함되지 않은 새로운 배열을 만드는 방식으로 해결할 수 있습니다.

문제 해결 접근 방식

이 접근법의 핵심은 배열을 순회하면서 첫 번째 0이 아닌 원소를 찾는 것입니다. 첫 번째 0이 아닌 원소부터 끝까지의 값들만 새로운 배열에 복사하면, 선행 0이 제거된 배열을 자연스럽게 얻을 수 있습니다.

알고리즘 단계

배열의 처음부터 순회하며 첫 번째 0이 아닌 원소의 인덱스를 찾습니다.
배열 전체가 0으로 이루어져 있다면 "Empty"를 출력합니다.
그렇지 않다면, 첫 번째 0이 아닌 인덱스부터 마지막 원소까지 새로운 배열에 복사합니다.
새로운 배열을 출력합니다.

C++ 구현 예제

#include <iostream>

using namespace std;

int main() {
    int arr[] = {0, 0, 0, 1, 2, 0, 4};
    int n = sizeof(arr) / sizeof(int); // 배열의 크기 계산
    int last = -1;
    for(int i = 0; i < n; i++) { // 첫 번째 0이 아닌 원소 탐색
        if(arr[i] != 0) {
            last = i;
            break;
        }
    }
    if(last == -1)
        cout << "Empty\n";
    else {
        int b[n - last]; // 새로운 배열 생성
        for(int i = last; i < n; i++) // 새 배열에 원소 복사
            b[i-last] = arr[i];

        for(int i = 0; i < n-last; i++) // 배열 출력
            cout << b[i] << " ";
    }
}

실행 결과

1 2 0 4

코드 상세 설명

프로그램은 먼저 배열 arr을 순회하면서 첫 번째 0이 아닌 원소의 인덱스를 찾아 변수 last에 저장합니다. 순회가 끝난 후 last가 여전히 -1이라면, 이는 배열 전체가 0으로만 구성되어 있다는 의미이므로 "Empty"를 출력합니다.

첫 번째 0이 아닌 원소의 인덱스를 찾았다면, 새로운 배열의 크기를 (n - last)로 계산할 수 있습니다. 이후 for 루프를 last부터 n 미만까지 실행하면서 해당 원소들을 새 배열에 삽입하고, 최종적으로 새 배열을 출력합니다.

복잡도 분석

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 새 배열을 생성하기 때문에 최악의 경우 O(n)이 됩니다.

결론

이번 글에서는 배열에서 선행 0을 제거하는 문제를 다루었습니다. 첫 번째 0이 아닌 원소를 찾아 새 배열을 구성하는 간단하고 효율적인 C++ 프로그램과 함께 전체적인 접근 방식을 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분에게 도움이 되었기를 바랍니다.