169. Majority Element

출처

Majority Element - LeetCode

[문제 설명]
제일 많이 나온 원소를 리턴하시오. 참고로 제일 많이 나온 원소는 절반 이상 나옵니다.

 

[처음 생각한 접근 방법]
1번 풀이
맵에 키는 숫자, 값은 숫자 개수로 넣어서 값이 n/2보다 커지면 키를 리턴. 매번 키를 넣을 때마다 map에서 조회를 하기 때문에 느림.

2번 풀이
1번이랑 똑같은 방식인데 맵에 값을 다 넣고 조회를 해줌. 맵에 값(숫자의 개수)가 절반보다 크면 answer은 그 키 값이 되고, 반복문을 빠져 나와서 반환함.

3번 풀이
정렬한 다음에 n/2후에 원소랑 첫번째 원소랑 같은지 비교. 같으면 첫번째 원소가 정답임.
같지 않으면 첫번째 원소랑 다른 원소가 나올 때까지 인덱스 증가.

 

[내가 쓴 코드]

//1번
import java.util.Arrays;

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int tempNum = 0;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            tempNum = nums[i];
            if (tempNum == nums[i + n/2]) {
                break;
            }
        }

        return tempNum;
    }
}

//2번
import java.util.HashMap;
import java.util.Map;

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

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

        for (int number : map.keySet()) {
            if (map.get(number) > nums.length/2) {
                answer = number;
                break;
            }
        }

        return answer;
    }
}

//3번
import java.util.Arrays;

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int tempNum = 0;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            tempNum = nums[i];
            if (tempNum == nums[i + n/2]) {
                break;
            }
        }

        return tempNum;
    }
}

리트코드 최다 추천 답안

public class Solution {
    public int majorityElement(int[] num) {

        int major=num[0], count = 1;
        for(int i=1; i<num.length;i++){
            if(count==0){
                count++;
                major=num[i];
            }else if(major==num[i]){
                count++;
            }else count--;

        }
        return major;
    }
}

알고리즘을 풀면서 느끼는 거지만 로직은 비슷한데 코드가 천차만별인 경우가 많은 거 같다.
이것도 풀어볼까 했던 방법인데, if else만 넘칠 거 같아서 포기했던 방법인데. 이걸 이렇게 깔끔하게 쓰네.