codekata7. 과반수인 요소 찾기

rahula·2021년 6월 29일
0

algorithm

목록 보기
7/9

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

문제파악

요구사항 : 숫자로 이루어진 배열에서 과반수가 넘는 숫자를 반환해라.

제한사항 : 없음

인풋 : 배열

아웃풋 : 숫자

본질 : 갯수세기 혹은 index 이용하기

딕셔너리를 이용해서 각 숫자가 배열안에서 몇개인지를 저장해라.
그리고 만약 그 숫자가 배열의 길이를 2로 나눈 값보다 크다면 그 숫자를 반환해라.

count함수를 써도 되기는 할듯.ㅋㅋ

첫번째 방법

set : 집합으로 만들기
count : 배열안에 숫자 갯수를 구해주는 함수.

def more_than_half(nums):
    for num in set(nums) :
      if nums.count(num) >= len(nums) / 2:
        return num
    return None

두번째 방법

def more_than_half(nums):
	max = 0
    for i in set(nums):
    	count = nums.count(i)
        if count > max:
        	max = count
            value = i
	return value

세번째 방법


def more_than_half(nums):
  my_dict = {}
  for num in nums:
    if num in my_dict:
      my_dict[num] += 1
    else :
      my_dict[num] = 1
    print(my_dict)
  for key, value in my_dict.items():
    if value >= len(nums)//2:
      return key
  return None

네번째 방법

문제점 : 홀수이고 한 숫자가 딱 과반일 경우, 다른 숫자가 들어갈 수 있다.


def more_than_half(nums):
  nums.sort()
  print(nums)
  print(len(nums) // 2)
  print(nums[len(nums) // 2])
  if len(nums) % 2:
    return nums[len(nums) // 2]
  else:
    return max(nums[len(nums) // 2 -1], nums[len(nums) // 2 +1])

다섯번째 방법

by 동명 선생님.

def more_than_half(nums):
	candidate, count = nums[0], 0
    for num in nums:
    	if num == candidate:
    		count += 1
        elif count == 0:
            candidate, count = num, 1
        else:
        	count -= 1
   	return candidate
profile
백엔드 지망 대학생

0개의 댓글