문제

숫자로 이루어진 배열인 nums를 인자로 전달합니다.

숫자중에서 과반수(majority, more than a half)가 넘은 숫자를 반환해주세요.

예를 들어,

nums = [3,2,3]
return 3

nums = [2,2,1,1,1,2,2]
return 2

가정

nums 배열의 길이는 무조건 2 이상입니다.

풀이

#1

가장 간단하고, 많이들 선택한 방법. 하지만 데이터의 양이 많아졌을 때의 running time은 길다.

# 요소 별 nums 내의 개수가 nums 전체길이의 반을 초과할 때 반환
def more_than_half(nums):
    for i in nums:
      if nums.count(i) > len(nums)/2:
        return i

여기서부턴, 리스트 내 개수가 과반수가 넘는 숫자가 반드시 존재한다는 가정 하의 풀이들이다.

#2

def more_than_half(nums):
  nums.sort()                  # 요소들을 순서대로 정렬
  return nums[len(nums)//2]    # 2로 나눈 몫을 인덱스로 갖는 값(정가운데 혹은 그의 하나 다음에 있는 값) 반환

#3

def more_than_half(nums):
  m = {}
  for n in nums:
    m[n] = m.get(n, 0) + 1
    if m[n] > len(nums) // 2:
      return n

dictionary.get(a, b)

• dictionary의 a라는 키에 해당하는 value 값을 반환하는 메소드 (dictionary[a] 와 비슷)
• dictionary[a]와 다른 점은,
  a 라는 key가 dictionary 내에 없을 경우, error를 발생시키지 않고 b라는 default 값으로 반환해준다.
• 예시:

>>> a_dict = {'hi': 1, 'bye': 2}
>>> a_dict.get('hi', 5)
1
>>> a_dict.get('oh', 5)
5
>>> a_dict
{'hi': 1, 'bye': 2}    # get으로 dictionary에 추가가 되진 않음

#4

def more_than_half(nums):
  count_dict = {}
  result = 0
  max_count = 0

  # dictionary 안에 요소 별 개수 저장
  for num in nums:
    if num not in count_dict:
      count_dict[num] = 1
    else:
      count_dict[num] += 1
      
    # 요소 별 개수를 계속 비교하며 저장
    if count_dict[num] > max_count:
      result = num
      max_count = count_dict[num]

    return result