C++로 배열에서 유일하게 다른 요소 찾기: 효율적인 풀이 방법

문제 설명

이번 문제에서는 크기가 n인 배열 arr[]가 주어지며, 우리의 목표는 배열에서 유일하게 다른 요소를 찾는 것입니다.

배열에는 두 가지 종류의 값만 존재하고, 단 하나의 요소를 제외한 나머지는 모두 동일한 값을 가집니다.

예시로 문제 이해하기

입력:

arr[] = {1, 1, 1, 2, 1, 1, 1, 1}

출력:

2

위 예시에서 2만 다른 값을 가지므로 정답은 2입니다.

문제 해결 접근 방법

방법 1: 완전 탐색 (O(N²))

가장 직관적인 방법은 배열을 순회하면서 각 요소를 다른 모든 요소와 비교하는 것입니다. 다른 값을 가진 요소를 발견하면 그 값을 반환합니다. 다만 이 방법은 시간 복잡도가 O(N²)이 되어 배열의 크기가 커질수록 비효율적이라는 단점이 있습니다.

방법 2: 해시 테이블 활용 (O(N))

해시 테이블(맵)을 사용해 각 요소의 등장 횟수를 저장한 뒤, 등장 횟수가 1인 값을 출력하는 방식입니다. 시간 복잡도는 O(N)으로 개선되지만, 추가적인 메모리 공간이 필요합니다.

방법 3: 인접 요소 비교 (O(N), O(1) 공간)

'배열에 두 종류의 값만 존재한다'는 조건을 활용하면 추가 메모리 없이도 선형 시간 안에 답을 구할 수 있습니다. 먼저 처음 세 개의 요소를 서로 비교해 다수를 이루는 기준값을 판별하고, 이후에는 인접한 요소들을 순차적으로 비교하여 값이 달라지는 지점의 요소를 반환하면 됩니다.

구현 예제

아래는 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.

#include <iostream>
using namespace std;

int findDiffElementArray(int arr[], int n){
    if (n == 1)
        return -1;
    if (n == 2)
        return arr[0];
    if (arr[0] == arr[1] && arr[0] != arr[2])
        return arr[2];
    if (arr[0] == arr[2] && arr[0] != arr[1])
        return arr[1];
    if (arr[1] == arr[2] && arr[0] != arr[1])
        return arr[0];
    for (int i = 3; i < n; i++)
        if (arr[i] != arr[i - 1])
            return arr[i];
    return -1;
}

int main(){
    int arr[] = { 5, 5, 1, 5, 5, 5, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The different element in the array is "<<findDiffElementArray(arr, n);
    return 0;
}

실행 결과

The different element in the array is 1

마무리

이처럼 배열에 두 종류의 요소만 존재한다는 특징을 활용하면, 해시 테이블 없이도 O(N) 시간과 O(1) 공간으로 유일하게 다른 요소를 효율적으로 찾을 수 있습니다. 배열의 길이가 짧거나(1~2개) 예외 상황을 처리하는 코드도 함께 포함되어 있어 실전에서 안정적으로 사용할 수 있습니다.