[LeetCode] 169. Majority Element

https://leetcode.com/problems/majority-element

개요

1. 정수 배열 nums와 배열의 크기 n이 주어진다.
2. 이 중 배열의 n / 2를 넘게 차지하는 원소를 찾아라

문제 해결 아이디어

• [2,2,1,1,1,2,2] 와 같이 배열이 주어졌을 때를 생각해보자.
  • 원소가 2에서 1로 바뀌고, 또 1에서 다시 2로 바뀐다.
  • 1에서 2로 바뀌는 시점에서 2의 카운팅 횟수를 기억하기 어렵다.

🧐 배열의 같은 값이 모아져 있으면 카운팅할 수 있을듯하다

➡️ 배열을 오름차순이나 내림차순으로 sorting 한다
➡️ 값이 달라지는 시점부터 카운팅을 시작한다.

의사 코드

1. 오름차순으로 nums를 정렬한다.
2. nums 배열을 돈다.
3. nums의 현재 원소와 직전 원소를 비교한다.
   3-1. nums의 현재 원소와 직전 원소가 다르다.
   3-1-1. count를 0으로 초기화
4. count의 값을 1 증가한다.
5. count가 (nums.length/2) 보다 큰지 확인한다.
   5-1. count가 (nums.length/2) 보다 크다.
   5-1-1. answer = 현재 원소
6. return answer

do 배열 오름차순으로 정렬
for(인덱스 = 0 to 배열 길이){
	if(현재원소 != 이전원소){
    	count = 0
    }
    count++
    if(count > 배열길이/2){
    	return 현재원소
    }
}

결과

전체 코드 github 링크

다른 풀이

public int majorityElement(int[] nums) {
         if(nums.length == 1) return nums[0];
        Arrays.sort(nums);  
        return nums[nums.length / 2];
    }

nums.length 를 체크해 연산할 필요가 없는 경우 빠르게 리턴했다.
어떤 원소가 nums의 과반수 이상을 차지한다면, 각각의 요소를 카운팅할 필요없이 중간 인덱스의 값은 무조건 해당 원소이다.
➡️ 문제의 숨겨진 원리를 파악해서, 불필요한 연산을 줄이자!