[1주차] 169. Majority Element

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

 

문제

주어진 정수배열 nums 에서 nums.size / 2 보다 많이 나오는 원소를 리턴한다. 단, 조건에 맞는 원소는 반드시 존재한다.

 

해결

문제를 보자마자 생각난 방식

fun majorityElement(nums: IntArray): Int {
    val map = mutableMapOf<Int, Int>()
    nums.forEach {
        val prev = map.getOrDefault(it, 0)
        map[it] = prev + 1
    }

    map.forEach {
        if (it.value > nums.size / 2) {
            return it.key
        }
    }

    return -1
}

• nums를 순회하면서 map에 담는다. key는 원소이고, value는 해당 원소의 개수이다.
• 그 이후 map을 순회하면서 가장 nums.size / 2 보다 크면 리턴한다.
• nums.size / 2 보다 큰 개수를 가진 원소가 두개가 존재할 수 없기 때문에 즉시 리턴한다.

 

하지만 문제 마지막 줄에

Could you solve the problem in linear time and in O(1) space?

 

 

???

 

선형시간에 해결하긴 했는데 상수 공간복잡도로 해결하라는 것은 Map 구조를 사용하지 말라는 소리다.

최악의 경우 map.size == n / 2 가 되기 때문에 공간복잡도가 O(n) 이기 때문이다.

 

잘 이해가 가지 않았다. 빈도수를 측정하기 위해선 반드시 각 원소별 개수를 기록해야만 할 것 같았다.

고민을 조금 해보니 배열 정렬과 주어진 조건을 조합하면 각 원소별 개수를 기록할 필요까진 없을 것 같았다.

 

아래의 방법은 O(1) 공간복잡도와 O(nlogn) 시간복잡도를 가진다.

전혀 아니다.. Kotlin의 Array.sort() 는 Java의 Arrays.sort() 를 호출하며, 이는 배열의 타입과 상황에 따라 다르지만 보통 O(n)의 공간복잡도를 사용한다.

DualPivotQuickSort() 의 분할 정복 과정에서 버퍼를 사용하기 때문이다.

즉, 밑의 알고리즘은 O(nlogn)의 시간복잡도와 O(n) 공간복잡도를 가진다.

실행결과도 map을 사용할 때 보다 시간과 공간 둘 다 좋지 못했다.

 

fun majorityElement(nums: IntArray) = nums.sorted()[nums.size / 2]

조건이 n / 2 보다 많은 개수의 원소이므로 정렬하고나면 오름차순이던 내림차순이던 반드시 중앙 인덱스를 넘어가기 때문이다.

 

하지만 애초에 정렬에 O(nlogn) 시간을 소비하므로 O(n) 시간복잡도와 O(1) 공간복잡도를 둘 다 만족할 수는 없다.

 

타 솔루션 참고

내 머리로 도저히 방법을 찾을 수 없어서 다른 사람의 솔루션을 가져왔다. 이 알고리즘은 시간복잡도 O(n) 과 공간복잡도 O(1)을 모두 만족한다.

fun majorityElement(nums: IntArray): Int {
     var majorityNum = nums[0]
     var cnt = 0
     nums.forEach {
         if (cnt == 0) majorityNum = it
         cnt += if (majorityNum == it) 1 else -1
     }

     return majorityNum
}

• majorityNum은 리턴할 최빈값이다.
• cnt는 현재 최빈값의 개수를 나타낸다. 최빈값이 아닌 수를 만나면 1 감소한다.

 

우리가 찾는 최빈값이 배열 곳곳에 흩어져서 majorityNum의 점유를 놓쳐버리는게 아닌가 하고 착각할 수 있다. 하지만 문제 조건상 최빈값은 num.size / 2 보다 크기 때문에 그렇지 않다.

 

또한 최빈값을 바꾸는 if문(5행) 이 카운터 변수 증감문(6행) 위에 위치한다. 즉, 카운터가 1인 상황에서 다른 원소가 최빈값 위치를 점유하기 위해서는 2번 더 나와야 한다.

[1,1,2,2,2], [2,2,2,1,1], [2,1,2,1,2,1,2,1,2], [1,2,1,2,1,2,1,2,2] 등, 어떠한 경우에도 반드시 성립한다.

 

천재적 발상이다