Majority Element

제출코드

없음

모범답안1

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return nums[n/2];
    }
}

• 다수 요소가 존재하는 배열에서, 오름차순 정렬 후, n/2의 인덱스에 해당하는 요소는 무조건 가장 많이 등장한 요소다. 이를 알지 못하면 풀기 상당히 어려운 문제이다.

• ex) {1,1,1,2,2,2,2} -> 7 / 2 = 3.5 -> 배열의 인덱스는 정수이므로, 여기서 n/2를 인덱스로 사용할 때는 3을 사용한다(인덱스는 0부터 시작하므로).
  -> 따라서, 인덱스 3에 위치한 요소는 2다. 이 배열에서 2는 4번 나타나므로, 배열의 크기의 절반보다 많다. 그래서 2가 이 배열의 다수 요소다.

• 하지만 이 방법은 O(n log n)이므로 비추천하는 방식이다.

모범답안2

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();

        for(int i =0; i < n; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }

        n = n/2;

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > n) {
                return entry.getKey();
            }
        }

        return 0;
    }
}

• map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
  map.put(key, value) 이다.
  value는 만약 key가 존재한다면 기존 값 + 1을 해야하고, 없으면 0을 넣어야 한다.
  따라서 map.getOrDefault(nums[i], 0) + 1의 의미는 nums[i]가 존재하면 해당 value에 +1을, 없으면 0을 가져온다는 것이다.

• V value = map.getOrDefault(key, defaultValue);: 찾고자 하는 키의 value를 가져오되, 만약 key가 없으면 defaultvalue를 가져온다.

Map<String, Integer> map = new HashMap<>();
map.put("apple", 10);
map.put("banana", 20);

int appleCount = map.getOrDefault("apple", 0); 
// 10을 반환 (키 "apple"이 존재함)
int orangeCount = map.getOrDefault("orange", 0); 
// 0을 반환 (키 "orange"가 존재하지 않으므로 기본값 반환)