다수 원소 II

출처: Dev.to

정수 배열 nums가 주어지면, ⌊n/3⌋ 번보다 많이 등장하는 모든 원소를 반환합니다.
원소는 n/3 번보다 많이 나타나야 합니다.
이는 최대 2개의 원소만 존재할 수 있음을 의미합니다.

왜일까요?
만약 서로 다른 3개의 원소가 각각 n/3 번보다 많이 등장한다면:
n/3 + n/3 + n/3 > n
가 되어 모순이 됩니다.

각 원소마다 배열을 다시 전체 탐색하면서 등장 횟수를 세어봅니다.
각 숫자를 개별적으로 확인하고, 그 빈도가 n/3 을 초과하는지 검증합니다.

시간 복잡도: O(N²)
공간 복잡도: O(1)

for(int i = 0; i  n/3) {
        // add if not already present
    }
}

HashMap을 이용해 빈도를 저장합니다.
반복해서 세는 대신, 모든 원소를 한 번씩만 세고 빈도가 n/3 초과인 원소를 모읍니다.

시간 복잡도: O(N)
공간 복잡도: O(N)

Map<Integer, Integer> map = new HashMap<>();

for(int num : nums) {
    map.put(num, map.getOrDefault(num, 0) + 1);
}

최대 2개의 다수 원소만 존재할 수 있으므로, 후보 2개와 그 카운트만 추적하면 됩니다.
세 개의 서로 다른 원소를 만나면 서로를 상쇄시키는 효과가 있습니다.
모든 상쇄가 끝난 뒤에 남는 것이 잠재적인 다수 원소가 됩니다.

알고리즘은 두 단계로 진행됩니다.

1. 두 후보를 찾는다.
2. 실제 빈도를 검증한다.

class Solution {
    public List<Integer> majorityElement(int[] nums) {

        int candidate1 = 0, candidate2 = 0;
        int count1 = 0, count2 = 0;

        for (int num : nums) {

            if (num == candidate1) count1++;
            else if (num == candidate2) count2++;
            else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            }
            else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            }
            else {
                count1--;
                count2--;
            }
        }

        count1 = 0;
        count2 = 0;

        for (int num : nums) {
            if (num == candidate1) count1++;
            else if (num == candidate2) count2++;
        }

        List<Integer> ans = new ArrayList<>();

        if (count1 > nums.length / 3) ans.add(candidate1);
        if (count2 > nums.length / 3) ans.add(candidate2);

        return ans;
    }
}

시간 복잡도: O(N)
공간 복잡도: O(1)

---

간단한 실행 예

입력:
[1,2,1,3,1,2,2]

투표 단계 후:

• candidate1 = 1
• candidate2 = 2

검증:

• 1 → 3번 등장
• 2 → 3번 등장

두 빈도 모두 7/3 = 2보다 크므로
답: [1, 2]

---

기억해 두면 좋은 패턴

• n/2 번보다 많이 → 후보는 최대 1개
• n/3 번보다 많이 → 후보는 최대 2개
• n/k 번보다 많이 → 후보는 최대 k‑1개

이 관찰은 Moore 투표 알고리즘 계열 문제들의 기본이 됩니다.