문제 개요
이 문제에서는 N개의 정수 값으로 구성된 배열 arr[]가 주어집니다. 우리의 목표는 배열에서 짝수 번 나타나는 첫 번째 요소를 찾는 프로그램을 작성하는 것입니다. 조건을 만족하는 요소가 존재하면 해당 값을 반환하고, 만약 없다면 false를 의미하는 -1을 반환해야 합니다.
예시를 통해 문제를 살펴보겠습니다.
입력: arr[] = {2, 3, 7, 2, 3, 6, 4, 1, 2}
출력: 3위 예시에서 3은 두 번 등장하며, 짝수 번 나타나는 첫 번째 요소이므로 출력 결과는 3이 됩니다.
해결 접근 방법
1. 단순 반복 탐색 방법
가장 직관적인 방법은 배열의 각 요소를 하나씩 확인하면서 해당 요소의 등장 빈도가 짝수인지 검사하고, 빈도가 짝수인 첫 번째 요소를 반환하는 것입니다. 다만 이 방법은 각 요소마다 전체 배열을 다시 확인해야 하므로 시간 복잡도가 O(N²)로 비효율적일 수 있습니다.
2. 해시 맵(Hash Map)을 활용한 효율적인 방법
보다 효율적으로 문제를 해결하려면 해시 맵 자료구조를 활용할 수 있습니다. 배열을 순회하면서 각 요소와 함께 그 등장 여부를 토글(toggle) 형태, 즉 true 또는 false 값으로 저장하는 해시 맵을 생성합니다. true는 홀수 번 등장했음을, false는 짝수 번(또는 아직 등장하지 않았음을 포함한 기준 상태) 등장했음을 나타내도록 구현할 수 있으며, 이렇게 하면 매번 빈도수를 다시 계산하는 오버헤드를 줄일 수 있습니다.
배열을 순회하면서 각 값 arr[i]에 대해 맵에 저장된 상태를 다음과 같이 처리합니다.
- 맵에 해당 값이 존재하지 않으면, 토글 값을 'true'로 설정하여 추가합니다(첫 등장 = 홀수 번).
- 맵에 해당 값이 존재하면, 현재 저장된 값을 반전시킵니다. 즉 'true'이면 'false'로, 'false'이면 'true'로 변경합니다.
배열 전체 순회가 끝난 후에는 다시 한번 배열을 처음부터 확인하면서 맵에서 토글 값이 'false'인, 즉 짝수 번 등장한 첫 번째 요소를 찾아 반환합니다. 모든 요소를 확인해도 조건을 만족하는 값이 없다면 -1을 반환합니다.
구현 예제
다음은 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
int findFirstEvenFreqVal(int arr[], int n){
unordered_map<int, bool> freqTogMap;
for (int i = 0; i < n; i++){
if (freqTogMap.find(arr[i]) == freqTogMap.end())
freqTogMap.insert(pair <int,bool> (arr[i],false));
else
{
bool val = freqTogMap.find(arr[i])->second;
if (val == true)
freqTogMap.find(arr[i])->second = false;
else
freqTogMap.find(arr[i])->second = true;
}
}
int j = 0;
for (j = 0; j < n; j++){
if (freqTogMap.find(arr[j])->second == true)
return arr[j];
}
return -1;
}
int main(){
int arr[] = { 2, 4, 6, 8, 1, 6 };
cout<<"배열에서 짝수 번 등장하는 첫 번째 요소는 " <<findFirstEvenFreqVal(arr, 6);
return 0;
}
실행 결과
배열에서 짝수 번 등장하는 첫 번째 요소는 6
정리
해시 맵을 활용하면 배열을 단 한 번의 주요 순회로 처리할 수 있어 시간 복잡도가 O(N)으로 크게 개선되며, 공간 복잡도는 O(N)입니다. 이처럼 토글 방식을 사용하면 빈도수를 직접 세지 않고도 짝수 번 등장 여부를 손쉽게 판별할 수 있다는 점이 핵심입니다.