C++에서 주어진 인덱스 범위 [L–R]의 배열 요소 삭제하기

배열에서 특정 인덱스 구간에 속한 여러 요소를 한 번에 삭제해야 하는 상황은 코딩 테스트나 실무 개발에서 자주 마주치게 됩니다. C++에는 이를 위한 별도의 내장 함수가 없지만, 두 개의 인덱스 변수를 활용한 반복문 하나만으로 O(n) 시간 안에 해결할 수 있습니다. 핵심 아이디어는 삭제 범위 밖에 있는 요소들만 앞쪽으로 당겨 덮어쓰는 것입니다.

1단계: 원본 배열과 삭제 범위 정의

먼저 원본 배열과 함께 삭제할 요소들의 배타적(exclusive) 범위 L, R을 정의하고, sizeof 연산자를 이용해 배열의 전체 길이를 계산합니다.

int arr[] = { 2,4,6,8,10,12,14,16,18,20 };
int L = 2, R = 6;
int length = sizeof(arr) / sizeof(arr[0]);

여기서 L = 2, R = 6이므로 인덱스 3~5에 해당하는 값(8, 10, 12)이 삭제 대상이 됩니다.

2단계: 범위 밖의 요소만 앞으로 이동

이제 배열을 처음부터 끝까지 순회하면서, 현재 인덱스 i가 L 이하이거나 R 이상인 경우(즉, 삭제 범위 밖인 경우)에만 해당 요소를 arr[k] 위치로 복사하고 k를 증가시킵니다. 반대로 i가 L과 R 사이에 있으면 그 요소는 건너뛰어지므로 결과적으로 삭제된 것과 같습니다. 루프가 모두 끝난 뒤 k값이 곧 새로운 배열의 길이가 됩니다.

int k = 0;
for (int i = 0; i < length; i++) {
    if (i <= L || i >= R) {
        arr[k] = arr[i];
        k++;
    }
}

전체 구현 예제

아래는 지금까지 설명한 알고리즘을 하나의 프로그램으로 완성한 코드입니다.

#include <iostream>
using namespace std;
int main() {
    int arr[] = { 2,4,6,8,10,12,14,16,18,20 };
    int L = 2, R = 6;
    int length = sizeof(arr) / sizeof(arr[0]);
    int k = 0;
    for (int i = 0; i < length; i++) {
        if (i <= L || i >= R) {
            arr[k] = arr[i];
            k++;
        }
    }
    length = k;
    for (int i = 0; i < length; i++)
        cout << arr[i] << " ";
    return 0;
}

실행 결과

위 코드를 컴파일하여 실행하면 다음과 같은 출력을 확인할 수 있습니다.

2 4 6 14 16 18 20

인덱스 3, 4, 5에 있던 값 8, 10, 12가 제거되고 나머지 요소들이 순서를 유지한 채 앞으로 당겨진 것을 볼 수 있습니다.

알고리즘 동작 과정

예제 데이터를 기준으로 단계별로 살펴보면 다음과 같습니다.

i = 0, 1, 2 → 조건(i ≤ L)을 만족하므로 2, 4, 6을 유지
i = 3, 4, 5 → L과 R 사이에 있으므로 8, 10, 12를 건너뜀(삭제)
i = 6, 7, 8, 9 → 조건(i ≥ R)을 만족하므로 14, 16, 18, 20을 유지

최종적으로 k = 7이 되며, 유효한 배열 길이도 7로 갱신됩니다.

시간 및 공간 복잡도

시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
공간 복잡도: O(1) — 추가 메모리 없이 원본 배열 내부에서 덮어쓰기 방식으로 처리합니다.

참고로 C++의 일반 배열은 크기가 고정되어 있으므로, 이 방식의 '삭제'는 물리적으로 메모리를 줄이는 것이 아니라 유효 길이를 k로 줄여 뒤쪽에 남은 값을 무시하는 논리적 삭제입니다. std::vector를 사용한다면 erase(v.begin()+L+1, v.begin()+R) 호출로 동일한 결과를 얻을 수 있습니다.