[Python] Code Kata Day7

문제

숫자로 이루어진 배열인 nums를 인자로 전달합니다.
숫자중에서 과반수(majority, more than a half)가 넘은 숫자를 반환해주세요.

예를 들어,

nums = [3,2,3]
return 3

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

• 가정
  nums 배열의 길이는 무조건 2개 이상

내코드

def more_than_half(nums):
  majority = len(nums)/2
  count = dict()
  
  for i in nums:
    if i in count:
      count[i]+=1
    else:
      count[i] =1
      
  for key, value in count.items():
    if value >= majority:
      return key

Model Solution

def more_than_half(nums):
	majority_count = len(nums)//2
	for num in nums:
		count = sum(1 for elem in nums if elem == num)
		if count > majority_count:
			return num

# 아니면 hashmap
import collections

def more_than_half(nums):
	counts = collections.Counter(nums)
	return max(counts.keys(), key=counts.get)

# 아니면 sort
def more_than_half(nums):
	nums.sort()
	return nums[len(nums)//2]

• 첫번째 방법
  • for문을 두 번 돌려서 하나의 요소가 리스트 안에 몇 개 있는지 센다(sum으로 나올때마다 1씩 더한다). sum이 과반수가 넘으면 바로 그 수를 return한다.
• 두번째 방법
  • collections.Counter로 리스트안에 어떤 숫자가 몇개 있는지 딕셔너리로 나타낸다. 그리고 max함수로 value가 가장 큰 key를 return한다.

    max(counts.keys(), key=counts.get)를 파헤쳐보자

    • Python dictionary method get() returns a value for the given key.
    • key (optional): key function to which each argument is passed and the comparison is done based on the value returned by this function

    즉, iterable한 object가 하나씩 돌면서 key로 주어진 함수에 들어가고 그 결과를 비교하여 max를 결정한다.

  • Collections.Counter, max function, get method
• 세번째 방법
  • 그냥 순서대로 쭉 정렬했을때 중간 보다 더 많은 수가 있는 것이 과반수이므로 중간 index에 있는 수를 확인한다.