C++로 배열에서 두 번 나타나는 모든 요소 찾기

문제 이해하기

정수 배열이 주어져 있고, 각 요소의 값은 1 ≤ a[i] ≤ n(n은 배열의 크기) 범위 안에 있다고 가정합니다. 이때 일부 요소는 두 번 나타나고, 나머지 요소는 한 번만 나타납니다. 목표는 두 번 나타나는 모든 요소를 찾아내는 것입니다.

예를 들어 배열이 [4,3,2,7,8,2,3,1]이라면, 2와 3이 두 번씩 등장하므로 출력 결과는 [2, 3]이 됩니다.

접근 방법: 부호 표시(Sign Marking) 기법

이 문제는 해시맵 같은 추가 자료구조 없이도 O(n) 시간 복잡도와 O(1) 추가 공간으로 해결할 수 있습니다. 핵심 아이디어는 배열 자체를 '방문 여부 기록판'으로 활용하는 것입니다.

배열의 값이 항상 1부터 n 사이이므로, 각 값은 배열의 유효한 인덱스에 대응됩니다. 어떤 값 v를 처음 만나면 인덱스 v-1 위치의 숫자를 음수로 바꿉니다. 그런데 나중에 같은 값을 또 만났을 때 해당 위치가 이미 음수라면, 이는 v가 한 번 더 등장했다는 뜻이므로 결과에 추가하면 됩니다.

알고리즘 단계

n을 배열의 크기로 설정하고, 결과를 저장할 배열 ans를 생성합니다.
i를 0부터 n-1까지 반복합니다.
- x := nums[i]의 절댓값을 구합니다.
- x에서 1을 빼서 인덱스로 변환합니다.
- nums[x]가 음수라면 이미 방문한 것이므로 x + 1을 ans에 추가합니다.
- 그렇지 않으면 nums[x]의 부호를 반전시켜(x + 1의 등장을 표시) 방문 처리를 합니다.
반복이 끝나면 ans를 반환합니다.

C++ 구현 예제

아래 코드를 통해 동작 과정을 더 명확히 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> findDuplicates(vector<int>& nums) {
      int n = nums.size();
      vector <int> ans;
      for(int i = 0; i < n; i++){
         int x = abs(nums[i]);
         x--;
         if(nums[x] < 0) ans.push_back(x + 1);
         else nums[x] *= -1;
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {4,3,2,7,8,2,3,1};
   print_vector(ob.findDuplicates(v));
}

입력

[4,3,2,7,8,2,3,1]

출력

[2,3]

동작 원리 살펴보기

입력 배열 [4,3,2,7,8,2,3,1]에 대해 알고리즘이 진행되는 과정을 간략히 추적해 보면 다음과 같습니다.

i = 0: 값 4 → 인덱스 3의 7을 음수로 변경
i = 1: 값 3 → 인덱스 2의 2를 음수로 변경
i = 2: 값 2 → 인덱스 1의 3을 음수로 변경
i = 3: 값 7 → 인덱스 6의 3을 음수로 변경
i = 4: 값 8 → 인덱스 7의 1을 음수로 변경
i = 5: 값 2 → 인덱스 1이 이미 음수(-3) → 2를 결과에 추가
i = 6: 값 3 → 인덱스 2가 이미 음수(-2) → 3을 결과에 추가
i = 7: 값 1 → 인덱스 0의 4를 음수로 변경

최종적으로 중복된 값인 [2, 3]이 반환되며, 절댓값 함수 abs() 덕분에 이미 부호가 변경된 요소를 다시 만나더라도 올바른 원래 값을 복원할 수 있습니다.

복잡도 분석

시간 복잡도: O(n) — 배열을 한 번만 순회합니다.
공간 복잡도: 출력 배열을 제외하면 O(1) — 입력 배열의 부호만 변경하여 방문 정보를 저장합니다.

C++로 배열에서 두 번 나타나는 모든 요소 찾기 — 부호 표시 기법 완벽 정리