C++로 1부터 N-1 사이의 유일한 반복 요소 찾기

문제 설명

이 문제에서는 크기가 N인 정렬되지 않은 배열 arr[]가 주어집니다. 배열에는 1부터 N-1까지의 값이 모두 포함되어 있으며, 그중 하나의 값이 두 번 나타납니다. 우리의 목표는 1부터 n-1 사이에서 유일하게 반복되는 요소를 찾는 것입니다.

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

입력

arr[] = {3, 5, 4, 1, 2, 1}

출력

1

풀이 방법 1: 브루트 포스(이중 반복문)

가장 직관적인 해결 방법은 배열을 순회하면서 각 값에 대해 동일한 요소가 배열의 다른 위치에도 존재하는지 확인하는 것입니다. 두 번 나타나는 값을 발견하면 해당 값을 반환하면 됩니다.

다만 이 방법은 구현이 간단한 대신 시간 복잡도가 O(N²)이므로, 배열의 크기가 커질수록 비효율적이라는 단점이 있습니다.

예제 1

아래 프로그램은 이 풀이의 동작 과정을 보여줍니다.

#include <iostream>
using namespace std;
int findRepValArr(int arr[], int n){
    for(int i = 0; i < n; i++)
    for(int j = i+1; j < n; j++)
    if(arr[i] == arr[j])
       return arr[i];
}
int main(){
    int arr[] = { 5, 3, 2, 6, 6, 1, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The repetitive value in the array is "<<findRepValArr(arr, n);
    return 0;
}

출력

The repetitive value in the array is 6

풀이 방법 2: 수학적 합 공식 활용

더 효율적인 접근 방식은 수학적 성질을 이용하는 것입니다. 배열에는 1부터 N-1까지의 값이 하나씩 존재하고 하나의 값만 두 번 나타나므로, 다음과 같은 관계가 성립합니다.

1부터 N-1까지 자연수의 합(S_n) = n × (n−1) / 2

doubleVal = 배열 전체의 합(arrSum) − S_n

즉, 배열 요소들의 실제 합에서 기대되는 합을 빼면 그 차이가 곧 두 번 나타나는 값이 됩니다. 이 방법은 배열을 한 번만 순회하면 되기 때문에 시간 복잡도가 O(N)으로 훨씬 효율적입니다.

예제 2

아래 프로그램은 합 공식을 활용한 풀이의 동작 과정을 보여줍니다.

#include <iostream>
using namespace std;
int findRepValArr(int arr[], int n){
    int arrSum = 0;
    for(int i = 0; i < n; i++)
       arrSum += arr[i];
    int sn = (((n)*(n-1))/2);
    return arrSum - sn;
}
int main(){
    int arr[] = { 5, 3, 2, 6, 6, 1, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The repetitive value in the array is "<<findRepValArr(arr, n);
    return 0;
}

출력

The repetitive value in the array is 6

정리

두 가지 방법 모두 문제를 정확히 해결할 수 있습니다. 브루트 포스 방식은 로직이 단순하지만 O(N²)의 시간이 걸리는 반면, 등차수열의 합 공식을 활용하는 방식은 O(N) 시간 안에 답을 구할 수 있어 실무적으로 더 권장됩니다.