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

이 튜토리얼에서는 두 번의 순회와 한 번의 순회, 두 가지 방식으로 C++ 배열에서 특정 요소를 삭제하는 방법을 알아봅니다. 여기서 말하는 '삭제'는 메모리에서 요소를 지우는 것이 아니라, 삭제할 요소 자리를 뒤에 있는 요소들로 한 칸씩 앞겹쳐 덮어쓰고 배열 크기를 1 줄이는 방식입니다.

1. 두 번의 순회(Two Traversals)

반복문 두 개를 사용해 배열에서 요소를 삭제하는 절차는 다음과 같습니다.

배열과 삭제할 요소를 초기화합니다.
요소를 삭제하는 함수를 작성합니다.
- 배열을 순회하며 삭제할 요소를 검색합니다.
- 요소를 찾으면 반복문을 종료(break)합니다.
- 요소가 존재하면 배열 크기를 1 감소시킵니다.
- 찾은 위치 뒤의 모든 요소를 이전 인덱스로 한 칸씩 이동시킵니다.
- 갱신된 배열 크기를 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int searchAndDeleteElement(int arr[], int n, int k) {
    int i;
    // 요소 검색
    for (i = 0; i < n; i++) {
        if (arr[i] == k) {
            break;
        }
    }
    // 요소가 존재하는 경우
    if (i < n) {
        // k 이후의 모든 요소를 이전 인덱스로 이동
        n = n - 1;
        for (int j = i; j < n; j++) {
            arr[j] = arr[j+1];
        }
    }
    // 갱신된 크기 반환
    return n;
}
int main() {
    int n = 6, k = 4;
    int arr[] = {1, 2, 3, 4, 5, 6};
    int updatedLength = searchAndDeleteElement(arr, n, k);
    // 배열 출력
    for (int i = 0; i < updatedLength; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

1 2 3 5 6

첫 번째 반복문에서 요소의 위치를 찾고, 두 번째 반복문에서 나머지 요소들을 앞으로 밀어주는 구조입니다. 시간 복잡도는 최악의 경우 O(n) + O(n)으로 두 번의 순회가 발생할 수 있습니다.

2. 한 번의 순회(One Traversal)

이번에는 반복문 하나만 사용해 같은 작업을 수행해 보겠습니다. 절차는 다음과 같습니다.

배열과 삭제할 요소를 초기화합니다.
요소를 삭제하는 함수를 작성합니다.
- 배열을 순회하며 삭제할 요소를 검색합니다.
- 요소를 처음 찾은 순간에는 해당 위치의 처리를 건너뛰고(continue), 찾았다는 플래그를 설정합니다.
- 요소를 찾은 이후부터는 모든 요소를 이전 인덱스로 이동시킵니다.
- 요소를 찾았다면 n - 1을 반환하고, 그렇지 않으면 n을 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int searchAndDeleteElement(int arr[], int n, int k) {
    // 마지막 요소인 경우 바로 처리
    if (arr[n-1] == k) {
        return n - 1;
    }
    bool isElementFound = false;
    for (int i = 0; i < n; i++) {
        // k를 처음 발견한 경우
        if (arr[i] == k && !isElementFound) {
            isElementFound = true;
            continue;
        }
        // 이미 요소를 찾았다면 뒤의 요소들을 앞으로 이동
        if (isElementFound) {
            arr[i-1] = arr[i];
        }
    }
    // 갱신된 크기 반환
    if (isElementFound) {
        return n - 1;
    }
    return n;
}
int main() {
    int n = 6, k = 4;
    int arr[] = {1, 2, 3, 4, 5, 6};
    int updatedLength = searchAndDeleteElement(arr, n, k);
    // 배열 출력
    for (int i = 0; i < updatedLength; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻습니다.

1 2 3 5 6

검색과 이동이 하나의 반복문 안에서 동시에 이루어지기 때문에, 두 번의 순회 방식보다 불필요한 재순회를 줄일 수 있습니다. 다만 마지막 요소가 삭제 대상일 경우를 별도로 처리해 주어야 인덱스 오류를 피할 수 있습니다.

마무리

정리하면, 두 번의 순회 방식은 로직이 직관적이고 이해하기 쉬운 반면, 한 번의 순회 방식은 검색과 이동을 함께 처리해 더 효율적입니다. 두 방식 모두 결과는 동일하게 1 2 3 5 6이 출력됩니다. 튜토리얼 내용 중 궁금한점이 있다면 댓글로 남겨주세요.