𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁

Leetcode 150 | Day 4: Majority Element

Leetcode 169는 배열에서 다수 요소(majority element)를 찾는 문제입니다. 다수 요소는 n / 2번보다 많이 나타납니다. 다수 요소는 항상 존재한다고 가정합니다.

두 가지 방법으로 해결할 수 있습니다.

방법 1: Map을 이용한 방식

이 방법은 Map을 사용하여 각 숫자가 몇 번 나타나는지 셉니다.

• 카운트를 저장할 Map을 생성합니다.
• 배열을 순회합니다.
• 각 숫자의 카운트를 업데이트합니다.
• Map을 순회하며 카운트가 n / 2보다 큰 숫자를 찾습니다.

복잡도:

• 시간 복잡도: O(n) (두 번의 순차적인 루프를 사용하기 때문)
• 공간 복잡도: O(n) (고유 요소의 수에 따라 Map의 크기가 커지기 때문)

방법 2: Boyer-Moore 투표 알고리즘 (Boyer-Moore Voting Algorithm)

이는 상수 메모리를 사용하여 문제를 해결하는 최적화된 방식입니다.

숫자를 서로 대립하는 팀이라고 생각해보세요. 어떤 숫자가 다른 숫자와 만날 때마다 서로를 상쇄시킵니다. 다수 요소는 전체의 절반 이상 나타나므로, 항상 마지막까지 살아남게 됩니다.

작동 방식:

• 후보(candidate)를 선택하고 카운트를 0으로 설정합니다.
• 배열을 순회합니다.
• 카운트가 0이면 현재 숫자를 후보로 설정합니다.
• 현재 숫자가 후보와 일치하면 카운트를 1 증가시킵니다.
• 일치하지 않으면 카운트를 1 감소시킵니다.

복잡도:

• 시간 복잡도: O(n) (배열을 한 번만 순회하기 때문)
• 공간 복잡도: O(1) (두 개의 변수만 사용하기 때문)

중요한 이유:

두 방법 모두 시간 복잡도는 O(n)입니다. 하지만 두 번째 방식은 메모리를 훨씬 적게 사용합니다. Map이 필요 없기 때문입니다. 따라서 대규모 데이터셋에 더 적합합니다.

출처: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6