[LeetCode/JAVA] 169. Majority Element

https://github.com/ROUTINE-STUDY/Algorithm

ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다.
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://leetcode.com/problems/majority-element/

Majority Element - LeetCode

문제 설명

출처 : LeetCode

배열이 주어집니다.
해당 배열의 요소중 과반수 이상 존재하는 요소가 존재합니다.
그 요소의 값을 반환하세요.

풀이 방법

다양한 방법으로 풀이했었습니다.
리팩토링 및 다양한 방법으로 풀이하다가 가장 많은 요소의 개수는 "배열의 길이 / 2" 보다 크다는 성질을 주로 활용
1. HashMap을 이용한 배열 전체 요소의 수 카운팅 후 위 성질을 이용하여 반환
2. 배열을 정렬 후 순서대로 카운팅 하여 위 성질에 충족하면 반환
3. 배열을 정렬하고 그 배열의 가운데 값은 무조건 과반수 요소

이 글에서의 코드는 최종 리팩토링 코드인 3번 코드를 기록하겠습니다. 
다른 코드는 깃허브 스터디에서 확인하실 수 있습니다.
https://github.com/ROUTINE-STUDY/Algorithm/pull/28/files 

내 코드(JAVA)

 

// majorityElement > nums.length/2 성질을 생각하다가 발견.. 
// 정렬을 한다면 nums.length/2의 인덱스에 있는 값은 무조건 majorityElement가 아니한가?
public int majorityElement(int[] nums) {
    int res = 0;

    // 원소가 1개이거나 2개이면 무조건 존재하는 원소가 majorityElement
    if(nums.length <= 2) return nums[0];

    // 정렬 후 가운데 값은 무조건 최대 원소
    Arrays.sort(nums);
    res = nums[nums.length / 2];

    return res;
}