C++에서 두 번의 순회와 한 번의 순회로 배열 요소 삭제하기

C++에서 배열은 고정된 크기를 가지기 때문에 특정 요소를 삭제하려면 해당 요소를 찾은 후, 뒤에 있는 요소들을 한 칸씩 앞으로 이동시키는 작업이 필요합니다. 이 글에서는 두 번의 순회를 사용하는 기본적인 방법과 단 한 번의 순회로 처리하는 최적화된 방법을 소개하고, 코드 예제를 통해 두 방식의 차이를 살펴보겠습니다.

두 번의 순회(Two Traversals)

먼저 원본 배열과 검색하여 삭제할 요소를 정의합니다.

int ele = 5;
int arr = [1,2,3,4];

이제 반복문을 사용해 배열을 처음부터 끝까지 탐색하며 주어진 요소가 있는 위치를 찾습니다.

for (i=0; i<length; i++)
    if (arr[i] == ele) break;

요소의 위치를 찾았다면, 해당 위치 오른쪽에 있는 모든 요소를 왼쪽으로 한 칸씩 이동시켜 빈자리를 메웁니다.

if (i < length) {
    length--;
    for (int j=i; j<length; j++)
        arr[j] = arr[j+1];
}

이 방식은 첫 번째 순회에서 요소를 찾고, 두 번째 순회에서 나머지 요소를 이동시키기 때문에 총 두 번의 순회가 발생합니다. 시간 복잡도는 O(n)입니다.

예제

다음 구현 예제를 통해 두 번의 순회로 배열에서 요소를 삭제하는 과정을 확인해 보겠습니다.

#include<iostream>
using namespace std;

int main() {
    int arr[] = {11, 15, 6, 8, 9, 10};
    int length = sizeof(arr)/sizeof(arr[0]);
    int ele = 6;

    int i;
    for (i=0; i<length; i++)
        if (arr[i] == ele) break;

    if (i < length) {
        length--;
        for (int j=i; j<length; j++)
            arr[j] = arr[j+1];
    }
    cout << "The array after deletion is "<<endl;
    for (int i=0; i<length; i++)
        cout << arr[i] << " ";

    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

The array after deletion is
11 15 8 9 10

한 번의 순회(One Traversal)

이번에는 같은 작업을 단 한 번의 순회로 처리하는 방법을 알아보겠습니다. 마찬가지로 원본 배열과 삭제할 요소를 먼저 정의합니다.

int ele = 15;
int arr = [11,15,6,8,9,10];

다음으로 요소 발견 여부를 저장하는 불리언 변수 found와, 요소를 찾았을 때 그 위치를 기록할 정수형 변수 pos를 선언합니다.

bool found=false;
int pos=-1;

이후 배열을 탐색하는 동안 요소를 발견하면 그 위치를 저장하고, 같은 반복문 안에서 바로 뒤따르는 요소들을 이동시킵니다. 이렇게 하면 검색과 이동 작업이 하나의 순회 안에서 동시에 이루어집니다.

for (int i=0; i<length; i++){
    if(pos!=-1){
        arr[pos]=arr[pos+1];
        pos++;
    }
    else if(arr[i]==ele){
        pos=i;
        found=true;
    }
}

이 방식 역시 시간 복잡도는 O(n)이지만, 요소를 찾은 후 추가 순회 없이 즉시 이동 작업을 수행하므로 실제 연산 횟수를 줄일 수 있습니다.

예제

다음 구현 예제를 통해 단 한 번의 순회만으로 배열에서 요소를 삭제하는 과정을 확인해 보겠습니다.

#include<iostream>
using namespace std;

int main() {
    int arr[] = {11, 15, 6, 8, 9, 10};
    int length = sizeof(arr)/sizeof(arr[0]);
    int ele = 6;

    bool found=false;
    int pos=-1;
    for (int i=0; i<length; i++){
        if(pos!=-1){
            arr[pos]=arr[pos+1];
            pos++;
        }
        else if(arr[i]==ele){
            pos=i;
            found=true;
        }
    }
    cout << "The array after deletion is "<<endl;
    if(found){
        length--;
    }
    for (int i=0; i<length; i++)
        cout << arr[i] << " ";
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

The array after deletion is
11 15 8 9 10