[코딩테스트] LeetCode - Majority Element (성공)

 

https://leetcode.com/problems/majority-element/description/?envType=problem-list-v2&envId=hash-table

Majority Element - LeetCode

 

 

풀이1

해시 테이블 문제라길래 c#의 Dictionary를 사용해서 문제를 풀어보려 했다. 

N은 최대 50,000

nums 배열을 0번째부터 하나씩 보면서 Dictionary에 빈도수를 저장, 저장된 빈도수가 n/2보다 크면 해당 숫자를 반환하면 되겠다. 

nums 배열을 0번째부터 하나씩 검사하므로 시간복잡도는 O(N)이 나온다. 

N은 최대 50,000이므로 1초 내로 풀 수 있다. 

O(N) 코드를 짜보자. 

 

 

코드1 - 오답

public class Solution {
    public int MajorityElement(int[] nums) {
        // majority element = 빈도수가 n/2보다 크면 majority element 

        // n은 최대 50000
        // O(N) 풀이로 nums배열을 0번째부터 하나씩 보면서
        // 빈도수를 저장
        // 빈도수를 저장하면 저장된 빈도수가 n/2보다 크다면 해당 숫자를 반환 

        // 빈도수를 저장하는 방법 = Dictionary 

        int n = nums.Length;
        Dictionary<int, int> dict = new Dictionary<int, int>(); // key = 숫자, value = 빈도수 
        for(int i = 0; i < nums.Length; i++)
        {
            // 처음 넣는 숫자이면 
            if(!dict.ContainsKey(nums[i]))
            {
                dict.Add(nums[i], 1);
            }
            // 이전에 넣었던 숫자이면 
            else
            {
                // 빈도수 증가 
                dict[nums[i]] = dict[nums[i]] + 1;

                if(dict[nums[i]] > (n / 2))
                {
                    return nums[i];
                }
            }
        }

        return -1;
    }
}

 

 

nums 배열에 원소 하나만 들어가 있을 경우 처리를 해주지 않아서 오답처리가 되었다. 

 

 

코드2 - 정답

public class Solution {
    public int MajorityElement(int[] nums) {
        int n = nums.Length;
        Dictionary<int, int> dict = new Dictionary<int, int>(); // key = 숫자, value = 빈도수 
        for(int i = 0; i < nums.Length; i++)
        {
            // 처음 넣는 숫자이면 
            if(!dict.ContainsKey(nums[i]))
            {
                dict.Add(nums[i], 1);
            }
            // 이전에 넣었던 숫자이면 
            else
            {
                // 빈도수 증가 
                dict[nums[i]] = dict[nums[i]] + 1;

                if(dict[nums[i]] > (n / 2))
                {
                    return nums[i];
                }
            }
        }

        if(n == 1)
        {
            return nums[0];
        }

        return -1;
    }
}

nums 배열 길이가 1일 경우(nums 배열에 원소가 하나만 들어가 있을 경우) nums의 첫번째 원소가 빈도수가 가장 많은 숫자이므로, nums[0]을 반환해주도록 수정했다. 

 

시간은 8ms, 메모리는 48MB를 사용했다. 

 

 

다른 사람 코드1

public class Solution {
    public int MajorityElement(int[] nums) {
        Array.Sort(nums);

        return nums[nums.Length / 2];
    }
}

nums 배열을 정렬하고 nums 배열 가운데 있는 숫자를 반환해주는 코드다. 

문제에서 빈도수가 많은 숫자는 빈도수가 무조건 n/2보다 크다고 했으므로, 정렬된 배열의 n/2번째 숫자는 무조건 빈도수가 많은 숫자가 된다. 

 

시간은 22ms, 메모리는 46MB를 사용했다. 

내 코드보다 시간이 더 걸렸다. 

Array.Sort의 시간복잡도는 O(NlogN)이라서 시간이 더 걸렸던 것 같다. 

그래도 문제에서 알려주는 정보(과반수 숫자는 n/2보다 크다)를 잘 활용한 것 같아 아이디어는 괜찮았다.

 

 

다른 사람 코드2

public class Solution {
    public int MajorityElement(int[] nums) {
        int Majority = 0;
        int Count = 0;
        for(int i = 0; i < nums.Length; i++)
        {
            if(Count == 0)
                Majority = nums[i];

            if(nums[i] == Majority)
                Count++;
            else
                Count--;
        }
        return Majority;
    }
}

 

시간은 0ms, 메모리는 46MB를 사용했다. 

거의 바로 정답을 찾아서 반환했다고 생각된다. 

이 알고리즘은 보이어-무어(Boyer-Moore) 알고리즘이라고 한다. 

서로 다른 두 원소를 1대 1로 비교하면서, 두 원소가 같으면 Count를 증가시키고, 두 원소가 다르면 Count를 감소시켜, 배열에서 과반수를 찾는 알고리즘이다. 

 

시간복잡도는 O(N)으로 내 코드와 동일하다. 

하지만 공간복잡도는 보이어-무어 알고리즘은 O(1), 내 코드의 공간복잡도는 O(N)이다. 

이유는 내 코드는 Dictionary를 사용한다. 만약 nums에 있는 숫자가 모두 다를 때 Dictionary에 모든 원소를 담아야 하므로 공간복잡도는 O(N)이다. 반면 보이어-무어 알고리즘은 변수 2개만을 이용하므로 공간복잡도는 O(1)이다. 

 

cf) 보이어-무어(Boyer-Moore) 알고리즘 = 수많은 데이터 중 과반수를 찾는 알고리즘. 과반수 데이터는 무조건 n/2 초과이다. 

 

 

복습1 풀이 (5/29)

배열 nums에서 가장 많이 나온 숫자를 반환하는 문제다. 

 

가장 먼저 떠올린 풀이는 nums[i]를 인덱스로 하여 빈도수를 저장하는 countArray에 빈도수를 저장하여 문제를 푸는 방식이었다. 

그러나 이 방법은 nums[i]의 값 범위때문에 불가능하다. 

 

과반수 숫자는 항상 n/2번 보다 많이 나온다고 한다. 그러면 nums배열을 정렬하고 가운데 숫자(n/2번째 숫자)가 과반수 숫자가 아닐까? 

예제2에서 nums = [2,2,1,1,1,2,2] 일때, nums배열을 정렬하면 [1,1,1,2,2,2,2]가 된다. 여기서 7/2=3. 3번째 인덱스 숫자는 2이다. 2는 과반수 숫자다. 그러니 nums배열을 정렬하고 가운데 숫자를 반환하면 되겠다. 

 

 

코드1 - 정답 

public class Solution {
    public int MajorityElement(int[] nums) {
        // 가장 많이 등장한 숫자 반환하기.  

        // 방법1
        // nums[i]를 인덱스로 하여 빈도수를 저장하는 countArray로 풀기. 
        // 이 방법은 nums[i]의 값 범위때문에 불가능. 

        // 방법2
        // nums배열 정렬, 가운데(nums.Length / 2)를 반환 
        // 시간복잡도 = O(N)? 
        nums.Sort();
        return nums[nums.Length / 2];
    }
}

 

 

25ms, 46MB가 나왔다. 

 

 

풀이2 

예전에 내가 풀었던 풀이를 다시 봤다. 

딕셔너리로 풀었던 풀이였는데, 이 방식은 좀전에 풀었던 방식보다 시간이 덜 걸렸다. 

정렬하는 과정 없이 순차적으로 검사하다가 빈도수가 n/2보다 큰 숫자가 나오면 그 숫자를 반환하기 때문이다. 

 

 

코드2 - 정답

public int MajorityElement(int[] nums) {
        // 방법3 
        // 딕셔너리 사용
        Dictionary<int, int> dict = new Dictionary<int, int>();
        for(int i = 0; i < nums.Length; i++)
        {
            if (!dict.ContainsKey(nums[i]))
            {
                dict.Add(nums[i], 1);
            }
            else
            {
                dict[nums[i]]++;

                if(dict[nums[i]] > nums.Length / 2)
                    return nums[i];
            }
        }

        if(nums.Length == 1)
            return nums[0];

        return -1;
    }

 

 

풀이3

보이어-무어 알고리즘으로 풀 수도 있었다. 

0ms, 46MB이다. 과반수를 찾는 문제에서는 보이어-무어 알고리즘을 적용하면 되겠다. 

 

 

코드3 - 정답 

public int MajorityElement(int[] nums) {
        // 방법4
        // 많은 데이터 중 과반수를 찾는 문제는 보이어-무어 알고리즘을 사용하면 된다. 
        // 시간복잡도는 O(N), 공간복잡도는 O(1)이다. 
        int majority = 0; 
        int count = 0; 
        for(int i = 0; i < nums.Length; i++)
        {
            if(count == 0)
                majority = nums[i];

            if(nums[i] == majority)
                count++;
            else
                count--;
        }

        return majority;
    }