C 언어에서 배열에 두 번 이상 나타나는 요소 찾는 방법

배열이란 무엇인가?

배열(Array)은 동일한 데이터 타입의 요소들을 연속된 메모리 공간에 저장하는 자료구조입니다. 배열의 크기(길이)는 선언 시점에 미리 정해져야 하며, 각 요소는 어떤 순서로든, 몇 번이든 나타날 수 있습니다. 이 글에서는 배열 안에서 두 번 이상 등장하는 요소(중복 요소)를 찾아 출력하는 방법을 다룹니다.

문제 설명

하나의 배열 arr[]가 주어졌을 때, 배열 안에서 반복적으로 나타나는 요소를 모두 찾아 화면에 출력하는 것이 목표입니다.

먼저 예제를 통해 문제를 이해해 보겠습니다.

입력: arr[] = {5, 11, 11, 2, 1, 4, 2}
출력: 11 2

위 예제에서 11과 2는 각각 두 번씩 나타나므로 결과로 출력됩니다. 반면 5, 1, 4는 한 번만 등장하기 때문에 결과에서 제외됩니다.

방법 1: 중첩 반복문을 이용한 비교

가장 직관적인 방법은 각 요소를 나머지 요소들과 하나씩 비교하는 것입니다. 바깥쪽 반복문으로 기준 요소를 선택하고, 안쪽 반복문으로 그 뒤에 있는 요소들과 값을 비교합니다. 같은 값을 가진 요소가 발견되면 해당 값은 중복이므로 출력합니다.

알고리즘

입력: arr[](배열), n(배열의 길이)
Step 1: i가 0부터 n-1까지 반복하며 Step 2 수행
Step 2: 각 요소마다 다음을 실행
    Step 2.1: j가 i+1부터 n-1까지 반복하며 Step 2.2~2.3 수행
    Step 2.2: if (arr[i] == arr[j]) → arr[i] 출력
    Step 2.3: else → 아무 작업도 하지 않음

C 구현 예제

#include <stdio.h>

int main() {
    int arr[] = {21, 87, 212, 109, 41, 21};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("배열에서 반복되는 요소 : ");
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] == arr[j]) {
                printf("%d ", arr[i]);
                break;  // 같은 요소가 여러 번 출력되지 않도록 함
            }
        }
    }
    return 0;
}

출력 결과

배열에서 반복되는 요소 : 21

이 방법은 구현이 간단하지만 두 개의 반복문을 사용하므로 시간 복잡도가 O(n²)입니다. 따라서 배열의 크기가 커질수록 성능이 저하될 수 있다는 점을 유의해야 합니다.

방법 2: 카운트 배열을 이용한 효율적 탐색

요소의 값 범위가 제한적이라면, 각 값의 등장 횟수를 기록하는 카운트 배열을 활용해 더 빠르게 해결할 수 있습니다. 배열을 순회하면서 처음 보는 값은 카운트를 1로 증가시키고, 이미 한 번 본 값(count가 1인 값)을 다시 만나면 그것이 중복 요소이므로 출력합니다.

C 구현 예제

#include <stdio.h>
#include <stdlib.h>

int main() {
    int arr[] = {21, 87, 212, 109, 41, 21};
    int n = sizeof(arr) / sizeof(arr[0]);
    int maxVal = 1000;  // 배열 요소의 최댓값보다 크게 설정

    int *count = (int *)calloc(maxVal, sizeof(int));

    printf("배열에서 반복되는 요소 : ");
    for (int i = 0; i < n; i++) {
        if (count[arr[i]] == 1)
            printf("%d ", arr[i]);   // 이미 한 번 등장한 값 → 중복
        else
            count[arr[i]]++;          // 첫 등장 → 카운트 증가
    }
    free(count);
    return 0;
}

출력 결과

배열에서 반복되는 요소 : 21

카운트 배열 방식은 배열을 한 번만 순회하면 되므로 시간 복잡도가 O(n)으로 매우 효율적입니다. 단, 요소 값의 최댓값만큼 추가 메모리가 필요하다는 점은 고려해야 합니다.

마무리

배열에서 두 번 이상 나타나는 요소를 찾는 대표적인 방법은 다음 두 가지입니다.

중첩 반복문 비교: 구현이 간단하지만 O(n²)의 시간 복잡도를 가집니다.
카운트 배열 활용: O(n)으로 빠르지만 값의 범위에 따라 추가 메모리가 필요합니다.

배열의 크기와 요소 값의 분포를 함께 고려하여, 상황에 맞는 방법을 선택하는 것이 좋습니다.