LeetCode : 169. Majority Element

문제 링크

문제 먼저 읽기

• 크기가 n인 nums 정수 배열이 주어집니다.
• 요소 안에서 과반수 요소인 정수를 반환합니다.
• O(1) 로 풀 수 있는 방법이 있는 것 같다.

Input: nums = [2,2,1,1,1,2,2]
Output: 2

어떻게 풀까?

생각

• nums가 정렬되어 있지 않다는 점을 어떻게 풀지 고민이 되었다.
• 각 숫자가 얼마나 나오는지 개수를 셀 수 있다. (Map collection 사용) 매번 이 방법을 사용해왔었다.
• 혹은 등장하는 숫자 개수가 2개이므로, 최소한의 변수로 과반수를 체크할 수 있지 않을까?

수도코드

class Solution {
    public int majorityElement(int[] nums) {
        int major = 0; // 과반수인 숫자를 저장한다.
				int count = 0;
				
				for (int i : nums) {
					if (count == 0) {
						major = i;
					}

					if (i==major) count ++; // 지금 숫자가 저장된 숫자와 같으면 count를 증가
					if (i!=major) count --; // 지금 숫자가 저장된 숫자와 다르면 count를 감소
				}

				return major; // 마지막으로 저장된 숫자를 반환한다.
    }
}

결과

<aside> 💡 Success

Runtime: 2 ms, faster than 67.58% of Java online submissions for Majority Element.

Memory Usage: 48.3 MB, less than 59.63% of Java online submissions for Majority Element.

</aside>

다른 풀이 방식과 문제 회고

class Solution {
    public int majorityElement(int[] nums) {
        return compare(nums, 0, nums[0]);
    }

    private int compare(int[] nums, int start, int value) {
        int count = 0;
        for(int i = start; i < nums.length; i++) {
            if(nums[i] == value)
                count++;
            else
                count--;
            if(count == -1)
                return compare(nums, i, nums[i]);
        }
        return value;
    }
}

• 가장 시간복잡도가 빠른 답변이다.
• 재귀를 이용한 부분은 생각치 못했었는데, 이렇게 풀 수도 있구나 싶다.