LeetCode 169 Majority Element

nayu1105·2023년 8월 23일

leetcode 알고리즘

LeetCode

목록 보기

5/28

LeetCode 169 Majority Element 풀러가기

문제

숫자가 들어있는 크기 n의 배열이 주어진다.

배열에서 majority 요소를 찾으면 되는데, majority요소란 배열에서 가장 많이 등장하는 요소로, ⌊n / 2⌋ 번 보다 많이 들어가 있는 요소이다.

문제 분석

첫번째 시도(소요시간 10분)

처음에는 각 nums 의 숫자를 index로 잡아서 count를 세는 배열을 만들까 했다.

그러나 문제에서 n == nums.length, 1 <= n <= 5 * 10^4, -10^9 <= nums[i] <= 10^9 조건이 있어서 10의 9승은 너무 크닥 생각하여 저 방법을 택하지 않았다.

두번째로 생각한 방법은 map을 생각한 방법이였다.

map의 key를 nums의 값으로 하고, value를 갯수로 저장했다.

nums를 순회하며 모든 값을 넣고, 만약 value가 ⌊n / 2⌋ 번 보다 많다면 for문을 벗어나도록 해서 시간을 줄이려고 했다.

map이 저장 된 후, map 을 돌며 value가 max인 key 값을 찾아냈다.

코드

import java.util.HashMap;
import java.util.Map;

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

        for(int i=0; i<nums.length; i++){
            if(map.containsKey(nums[i])){
                if(map.get(nums[i])>=nums.length/2+1)break;
                map.put(nums[i], map.get(nums[i]) + 1 );
            }else{
                map.put(nums[i], 1);
            }
        }

        int answer = -1;
        for(Integer key : map.keySet()){
            if(answer == -1) {
                answer = key;
                continue;
            }

            if(map.get(key)>map.get(answer)){
                answer = key;
            }
            
        }

        return answer;

        
    }
}

결과 : 성공

Runtime

Memory

메모리는 괜찮았는데, 시간을 더 줄일 수 있는 방법이 없을까 고민이 되었다.

두번째 시도(소요시간 5분)

map에 저장한 후 다시 map을 순회하는 시간을 줄이려고 했다.
문제에서 주어진 조건을 보고, nums를 순회하며 map에 저장할 때 value 값이 ⌊n / 2⌋ 인 값이 있다면 바로 결과를 리턴하는 함수를 짰다.

_코드

import java.util.HashMap;
import java.util.Map;

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

        int check = nums.length/2;
        if(nums.length % 2 !=0){
            check++;
        }

        for(int i=0; i<nums.length; i++){
            if(map.containsKey(nums[i])){
                if(map.get(nums[i])+1==check){
                    return nums[i];
                }
                map.put(nums[i], map.get(nums[i]) + 1 );
            }else{
                map.put(nums[i], 1);
            }
        }
		
        // nums length 가 1인 경우
        return nums[0];        
    }
}