문제 개요
이 문제에서는 n개의 정수로 이루어진 배열 arr가 주어집니다. 우리의 과제는 배열에서 첫 번째 반복 요소(first repeating element)를 찾는 것입니다.
여기서 '첫 번째 반복 요소'란 배열 안에서 두 번 이상 등장하는 값들 중, 그 첫 등장 위치(인덱스)가 가장 앞선 값을 의미합니다.
예제로 이해하기
입력 : arr[] = {4, 1, 8, 9, 7, 2, 1, 6, 4}
출력 : 4설명 −
두 번 이상 등장하는 정수는 4와 1입니다.
4의 첫 등장 위치가 1보다 앞서므로 정답은 4입니다.
해결 방법 1: 중첩 반복문 사용
가장 직관적인 방법은 중첩 반복문을 사용하는 것입니다. 바깥쪽 반복문으로 배열의 각 정수를 하나씩 순회하고, 안쪽 반복문으로 현재 값과 동일한 다른 요소가 배열에 존재하는지 확인합니다. 동일한 값을 발견하면 즉시 해당 값을 반환하면 됩니다.
이 방법은 구현이 간단하지만, 반복 요소가 없는 최악의 경우 모든 요소 쌍을 비교해야 하므로 O(N²)의 시간 복잡도를 가집니다.
해결 방법 2: 해싱(Hashing) 활용
더 효율적으로 문제를 해결하려면 해싱을 활용할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열을 마지막 인덱스부터 거꾸로 순회합니다.
- 현재 요소가 이미 방문한 적 있다면, 그 인덱스를 '반복 요소 후보'의 최소 인덱스로 갱신합니다.
- 아직 방문하지 않았다면 집합에 추가합니다.
거꾸로 순회하면서 갱신하기 때문에 순회가 끝났을 때 남아 있는 최소 인덱스가 곧 '첫 번째 반복 요소'의 위치가 됩니다. std::set을 사용하면 O(N log N), std::unordered_set을 사용하면 평균 O(N)의 시간 복잡도로 해결할 수 있어 중첩 반복문 방식보다 훨씬 효율적입니다.
구현 코드
다음 프로그램은 위 해싱 방식의 동작을 보여줍니다.
#include<bits/stdc++.h>
using namespace std;
int findRepeatingElementArray(int arr[], int n){
int minRetIndex = -1;
set<int> visitedElements;
for (int i = n - 1; i >= 0; i--){
if (visitedElements.find(arr[i]) != visitedElements.end())
minRetIndex = i;
else
visitedElements.insert(arr[i]);
}
if (minRetIndex != -1)
return arr[minRetIndex];
else
return -1;
}
int main(){
int arr[] = {4, 1, 6, 3, 4, 1, 5, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"반복되는 요소는 "<<findRepeatingElementArray(arr, n);
}
실행 결과
반복되는 요소는 4
마무리
정리하면, 주어진 배열 {4, 1, 6, 3, 4, 1, 5, 8}에서 두 번 이상 등장하는 값은 4와 1이며, 4의 첫 등장 위치가 더 앞서므로 출력 결과는 4입니다. 반복 요소가 전혀 없는 경우 함수는 -1을 반환하도록 처리했습니다. 간단한 구현에는 중첩 반복문도 충분하지만, 입력 크기가 커질 수록 해싱 기반 접근이 성능 면에서 큰 이점을 제공합니다.