[leetcode - Java] 169. Majority Element

1. 문제

---

• 배열에서 가장 많이 등장하는 원소를 구하는데 해당 원소의 개수가 전체 배열의 n/2개를 넘는 것을 구하여라
  

2. 시도

---

첫 번째
이번 문제를 보고 어렵다고 느꼈다. 당장 머리에 떠오른건 전체 원소들의 개수를 각각 구해야하나? 라는 생각이었고, map으로 배열에서 나오는 첫 숫자들을 키값으로 저장해봤다.

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);

        HashMap<Integer, Integer> map = new HashMap<>();
        int index = 1;
        List<Integer> list = Arrays.stream(nums)
                .boxed()
                .collect(Collectors.toList());

        System.out.println("list = " + list);

        for (int i=0; i<nums.length; i++) {
            map.put(nums[i], Collections.frequency(list,nums[i]));
            index++;
        }

        int maxValue = Collections.max(map.keySet());
        System.out.println("map = " + map);

        return maxValue;
    }
}

일부 테스트 케이스는 성공했지만 성공 개수가 많지 않다.
예상되는 실패 이유는, 가장 큰 key가 출력되고 있기 때문이다.

두 번째

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);

        HashMap<Integer, Integer> map = new HashMap<>();
        int index = 1;
        List<Integer> list = Arrays.stream(nums)
                .boxed()
                .collect(Collectors.toList());

        System.out.println("list = " + list);

        for (int i=0; i<nums.length; i++) {
            map.put(nums[i], Collections.frequency(list,nums[i]));
            index++;
        }

        Integer maxKey = null;
        Integer maxValue = Integer.MIN_VALUE;
        for (Integer key : map.keySet()) {
            if (maxKey == null || map.get(key) > maxValue) {
                maxKey = key;
                maxValue = map.get(key);
            }
        }
        System.out.println("map = " + map);
        System.out.println("maxKey = " + maxKey);

        return maxKey;
    }
}

성공 케이스가 눈에 띄게 많아졌지만 오류는 Wrong Answer에서 Time Limit Exceeded로 바뀌었다. 아무래도 각 key를 검사하는 새로 추가한 반복문이 문제인 듯하다.

3. 개선

• map을 사용하지 않고 입력받은 배열로 문제를 해결해보자.

---