배열에서 모든 중복 요소 찾기 (C++)

Source: Dev.to

Problem Summary

배열에서 두 번 이상 나타나는 모든 요소를 찾아서 각 중복 요소는 한 번만 출력합니다.

Example

Input:  [1, 2, 3, 2, 4, 1]
Output: [1, 2]

Approach 1: Frequency Array

가능한 값들의 범위가 알려져 있고 비교적 작을 때 사용하는 방법입니다.

#include 
using namespace std;

int main() {
    vector n = {1, 2, 3, 2, 4, 1};
    vector out;
    vector tracker(100, 0);   // 값 범위에 맞게 크기를 조정

    for (int x : n) tracker[x]++;

    for (size_t i = 0; i  1) {
            out.push_back(static_cast(i));
        }
    }
    // `out` now contains the duplicate values
}

Complexity

• Time: O(n + k) 여기서 n은 요소 개수, k는 값 범위의 크기입니다.
• Space: O(k) – 빈도 배열을 위한 공간.

When to Use

• 값 범위가 작고 미리 알려져 있어 빈도 배열을 만들 수 있을 때.
• 가능한 가장 빠른 조회가 필요할 때.

Approach 2: Using unordered_map

값 범위가 어떻든 상관없이 사용할 수 있는 방법입니다.

#include 
#include 
using namespace std;

int main() {
    vector n = {1, 2, 3, 2, 4, 1};
    vector out;
    unordered_map tracker;

    for (int x : n) tracker[x]++;

    for (const auto& it : tracker) {
        if (it.second > 1) {
            out.push_back(it.first);
        }
    }
    // `out` now contains the duplicate values
}

Complexity

• Time: 평균 O(n) (해시 테이블 연산).
• Space: O(n + z) 여기서 z는 서로 다른 중복 값의 개수입니다.

When to Use

• 가능한 값들의 범위가 알려져 있지 않거나 매우 클 때.
• 입력 도메인에 관계없이 유연하게 동작하는 솔루션을 원할 때.

Key Comparison

Final Takeaway

두 방법 모두 중복 요소를 정확히 찾아냅니다.
값 범위가 제한적이고 최대 속도가 필요하면 빈도‑배열 방식을 선택하세요.
값 범위가 알 수 없거나 크다면 unordered_map 방식을 선택하되, 약간의 추가 메모리 사용을 감수하면 됩니다.

왜 특정 접근 방식을 선택하는지가 코드 자체보다 더 중요한 경우가 많습니다.