[leetcode 169] Majority Element

169. Majority Element

https://leetcode.com/problems/majority-element/

해결 과정

입력으로 주어진 Int 배열, nums 의 for문을 돌면서 HashMap에 <Int, 등장 개수> 를 저장하고, 주어진 배열 개수/2 보다 등장 개수가 더 크면 해당 Int를 반환하도록 했다.

코드 1

fun majorityElement(nums: IntArray): Int {
  val size = nums.size
  if(size == 1)
    return nums[0]
        
  val map = hashMapOf<Int, Int>()
  nums.forEach { num ->
    if(map.containsKey(num)) {
      map.put(num, map[num]!!.plus(1))
      if(map[num]!! > size/2) {
        return num
      }
    } else {
      map.put(num, 1)
    }
  }
  return -1 // no case here
}

코드 2

fun majorityElement(nums: IntArray): Int {
  val size = nums.size
  val map = hashMapOf<Int, Int>()
  nums.forEach { num ->
    if(map.containsKey(num)) {
      map.put(num, map[num]!!.plus(1))
    } else {
      map.put(num, 1)
    }    
    if(map[num]!! > size/2) {
      return num
    }
  }
  return -1 // no case here
}

배운 점

모든 문제를 풀 때 엣지케이스에 대해서 생각해보자.

• 코드1: 엣지 케이스는 nums 개수가 1개 일때로, for문이 시작하기전 size 검사 후 첫번째 원소를 반환

HashMap 의 containsKey() 코드 조각이다.

public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
}

입력 key 를 가졌을때만 true 를 반환하며, 위의 문제에서 nums 원소로 null 이 포함되지 않기 때문에 !! 를 사용했다.

---

코드1 에서는 map 이 원소를 가지고 있을때만 if(map[num]!! > size/2) 조건 비교를 하고, 코드2 에서는 매 원소마다 조건 비교를 했다.

return 값에 대한 비교를 언제 진행하냐에 따라 1) 비교 연산의 횟수가 달라지며 2) 엣지케이스가 생기기도, 안생기기도 한다.