리트코드 - 169. Majority Element

리트코드 - 169. Majority Element

출처 - https://leetcode.com/problems/majority-element/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 크기가 n인 배열 nums가 주어지며, 과반수 원소를 반환합니다.

과반수 원소란 배열에서 ⌊n / 2⌋번 이상 나타나는 원소를 의미합니다. 주어진 배열에 항상 과반수 원소가 존재한다고 가정할 수 있습니다.

의사코드

map 생성 반복문 시작(nums 순회)     map에 key 값과 nums가 일치하면 value에 +1 추가 반복문 종료 최대값을 0으로 생성 과반수 원소 k값을 0으로 생성 반복문 시작(map순회)     만약 최대값보다 value가 크면         최대값에 value를 저장 반복문 종료

풀이코드

import java.util.*;

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

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

        int max = 0;
        int k = 0;

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int value = entry.getValue();

            if (max < value) {
                max = value;
                k = entry.getKey();
            }
        }
        
        return k;
    }
}

코드설명

map에 key값은 유일한 값이고, value는 중복이 허용되는 특성을 이용하기위해 map구조를 사용하였다.

배열을 순회하면서 각 요소들을 map의 key값으로 정하여 key값이 있을때마다 1씩 더해주었다.

즉, key가 있는 값들은 1 이상의 value를 가지게 된다.

 

이후에는 map을 key와 value를 가진 entrySet으로 바꾸어주고 순회하며 max값을 찾는다.

max값은 0으로 초기화를 하고, max값이 갱신되면 k에 key값을 넣었다.

 

시간복잡도 - O(n)

공간복잡도 - O(n) (map을 사용하였기 때문에 O(n)만큼의 공간복잡도를 가진다.)

문제를 풀며 생각한 흐름과 배운 점

예전에 백준에서 비슷한 문제를 풀어봤던 경험이 있었다.

풀고나니 런타임은 11ms로 빠른 편이었는데, 메모리에서는 O(n)을 쓰다보니 그렇게 효율이 좋지 못했다.

익숙하게 풀었지만 map과 entry에 대해서 몇가지 궁금증이 생겨서 정리해보려고 한다.

 

1. map에서 getOrDefault를 쓰는 이유

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();

        System.out.println("key: " + map.get("key"));  // 결과 key : null
        System.out.println("key: " + map.getOrDefault("key", "default"));   // 결과 key : default
    }
}

이 코드를 만들어보면 심플하게 이해가 된다.

map을 선언하게되면 "key"라는 값에는 아무런 값이 없기 때문에 map.get("key")를 하게되면 null 값을 반환하게 된다.

그 무서운 NPE다... 백엔드 개발자는 널을 싫어해야 한다....

그래서 이러한 null 값이 없는 경우 NPE가 안나도록 기본값을 정해주는 메소드가 getOrDefault 메소드다.

그럼 map에서 진짜 key와 value가 추가된건가?

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();

        System.out.println("key: " + map.get("key"));  // 결과 key : null
        System.out.println("key: " + map.getOrDefault("key", "default"));   // 결과 key : default
    	
        System.out.println("key: " + map.get("key"));  // 결과 key : null
    }
}

놀랍게도 맨 아랫줄은 다시 null이 나온다...

이는 map 자체를 바꾸는게 아니라 값이 null일 때 처리만 해주는 것이다.

반드시 put을 이용해서 값을 넣어줘야 함을 잊지 말자...

 

2. Map.Entry

오라클의 자바 8 공식문서를 보면 Map.Entry는 아래와 같이 정의되어 있다.

 

 

Nested Class Summary 항목에 있는데 이것은 Class 내부에 선언된 Class를 의미한다.

그래서 Map 클래스로 직접 접속해보면 아래와 같이 interface로 선언되어 있는 것을 볼 수 있다.

 

 

map은 순서를 보장하지 않고 저장하는 구조이기 때문에 이를 순서대로 뽑아 쓸수있는 Set 형태의 entrySet() 메소드를 제공하고 있고, 이 하나하나의 요소들은 Entry로 뽑아서 사용할 수 있다.

정확히는 Map.Entry(Map도 인터페이스이므로) 타입으로 사용이 가능하다.

 

3. 다른코드

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

역시 문제에서 힌트가 있었다.

과반수 원소란 배열에서 ⌊n / 2⌋번 이상 나타나는 원소를 의미합니다. 라는 문맥에서 그냥 오름차순 정렬을 하라는 의미였다는 걸 깨달았다.

오름차순을 하고, 가운데 값만 가져오면 되는 것이었다.

시간복잡도는 O(n * log n) 이고, 공간복잡도는 O(n) 이다.

 

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

    if(nums.length == 1) return nums[0];
         Arrays.sort(nums);
        int count1 = 0 , temp1 = nums[0] ;
        for (int i = 0; i <= nums.length - 1; i++) {
            if (temp1 == nums[i]) {
                count1++;
            }else {
                temp1 = nums[i];
                count1 = 1;
            }
            if ( count1  >= nums.length / 2.0)
                return temp1;
        }
        return temp1; 
	}
}

두번째 방법은 map을 이용하지 않는 방법이다.

이역시 Arrays.sort를 쓰고 있어 시간복잡도는 O(n log n) 이지만, 공간복잡도는 O(1)이다.

정렬이 되어있기 때문에 순차적으로 순회하면서 count를 하고 count의 값이 length의 절반을 넘으면 값을 리턴하고 있다.

 

그러면 시간복잡도는 O(n)이면서 공간복잡도는 O(1)인 방법은 없을까...

찾아보니 이번 코딩문제에선 값의 조건이 ±1억개기 때문에 사용하기 힘들지만 값이 작은 경우 사용할 수 있는 계수 정렬이라는 것도 있다.

 

1. 먼저 등장하는 값 중 최댓값 + 1에 해당하는 카운팅 배열을 만든다.
2. 원래 배열을 순회하며 그 값을 인덱스로하여 카운팅 배열[인덱스]에 +1 씩 추가해 준다.
3. 카운팅 배열을 누적합 배열로 바꾸어준다.
4. 이번에는 원래 배열을 거꾸로 순회하며 카운팅 배열[인덱스]에서 그 값을 확인한다.
5. 누적합 배열이기 때문에 그 값 자체가 인덱스가 된다.
6. 원래 배열 크기만큼의 새로운 배열을 만들어서 [인덱스] 부분에 순회하던 값을 저장하고 카운팅 배열에서 값을 -1 해준다.
7. 반복

출처 - Counting Sort : 계수 정렬

 

정리

특정한 상황을 제외하면 Arrays.sort()가 빠른 정렬 방법이다.(쿽 or 병합을 사용하므로)

문제에서 힌트를 주는 것을 절대 놓치지 말자...