[정렬] LeetCode 169번 문제 학습

문제 설명

Majority Element는 정수 배열 nums에서 과반수(majority)를 차지하는 요소를 찾는 문제임.

과반수 요소는 배열 길이 n 기준으로 n/2번 초과해서 등장하는 숫자임

• nums = [3,2,3] → 3이 답 (3이 두 번 나와서 n/2 = 1.5 초과).
• nums = [2,2,1,1,1,2,2] → 2가 답 (2가 네 번 나와서 n/2 = 3.5 초과).
• 배열 길이 n은 1 이상.
• 항상 과반수 요소가 존재함. 이게 중요! 따로 체크 안 해도 답이 무조건 있음.
• 시간복잡도 O(n log n) 이하로 풀면 좋고, 가능하면 O(n)으로 푸는 게 이상적.
• 공간복잡도는 O(1)로 최소화하는 방법도 있음.

문제를 푼 과정

1. 정렬 함수 (sortExample)
   • sort.Slice 써서 배열 nums를 오름차순으로 정렬함.
   • 비교 함수 func(i, j int) bool에서 exampleSlice[i] < exampleSlice[j]로 작은 값이 앞으로 가게 설정.
   • Go의 sort.Slice는 내부적으로 퀵소트 기반이라 안정적이고 빠름.
2. 과반수 요소 찾기 (majorityElement)
   • 정렬된 배열에서 가운데 요소 nums[len(nums)/2]를 리턴.
   • 왜 이게 답이냐면, 과반수 요소는 배열의 절반 넘게 등장하니까 정렬 후엔 무조건 가운데 위치에 있을 수밖에 없음.
   • 예를 들어, nums = [2,2,1,1,1,2,2] 정렬하면 [1,1,1,2,2,2,2] 되고, 가운데는 2임.

---

어떤 알고리즘 썼는지

정렬(Sorting) 기반으로 풀었음

1. 정렬 알고리즘
   • Go의 sort.Slice는 퀵소트 기반으로 평균 시간복잡도 O(n log n).
   • 배열을 정렬하면 과반수 요소가 배열 길이의 절반 이상을 차지하니까, 정렬된 배열의 중간 인덱스(n/2)에 반드시 그 요소가 있음.
   • 이 접근법은 간단하지만, 정렬 때문에 시간복잡도가 O(n log n)임.
2. 인덱싱
   • 정렬 후 nums[len(nums)/2]로 바로 답 뽑음. 이건 O(1) 작업.
   • 정렬만 끝나면 추가 연산 거의 없음.

다른 방법들

• 해시맵: 각 숫자의 등장 횟수 세기. 시간 O(n), 공간 O(n).
• Boyer-Moore Voting Algorithm: 과반수 요소를 O(n) 시간, O(1) 공간으로 찾음. 이게 최적.
• 근데 정렬 방식은 코드가 직관적이고, 문제 조건(항상 답 존재) 덕에 충분히 효율적임.

package main

import (
	"sort"
)

func majorityElement(nums []int) int {
	sort.Ints(nums)
	return nums[len(nums) / 2]
}

func main() {
}

Boyer-Moore 버전

package main

import "fmt"

func majorityElement(nums []int) int {
	candidate, cnt := nums[0], 1
	for _, num := range nums[1:] {
		if cnt == 0 {
			candidate = num
		}
		if num == candidate {
			cnt ++
		} else {
			cnt --
		}
	}
	return candidate
}

func main() {
	nums := []int{2, 2, 1, 1, 1, 2, 2}
	fmt.Println(majorityElement(nums))
}