[Python] (문제풀이) 배열의 숫자 중 과반수 반환하기

이태권 (Taekwon Lee)·2022년 6월 15일
0
post-thumbnail

"민중을 이끄는 자유의 여신" (외젠 들라크루아, 1830)


배열의 숫자 중 과반수 반환하기


❓ 문제

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

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

예를 들어,

nums = [3,2,3]
return 3

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

가정

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


🤔 접근 방식

  • 과반수(過半數)란, 말 그대로 배열 중에서 절반을 넘는 개수를 가진 숫자이다.
  • 즉, 정렬을 하고 절반에 위치한 인덱스를 뽑으면 그 숫자는 무조건 과반수이다.
    • 해당 배열(리스트)을 sort를 이용하여 오름차순으로 정렬한 다음,
    • 배열의 절반에 해당하는 인덱스를 반환한다.

❗️ 답안

내 답안

def more_than_half(nums):
  nums.sort()
  return nums[len(nums)//2]

문제점

  • 다만, 과반수가 없는 배열이어도 아무 숫자가 반환될 수 있다는 것이 문제이다.
  • 과반수가 없을 때 None을 리턴할 수 있도록 알고리즘을 짜면 더 좋을 것 같다

다른 답안 1

  • 아래 답안은 max()를 활용하여 제일 개수가 많은 숫자를 반환하도록 알고리즘이 짜여져 있다.
  • setdictionary를 활용해서 푼 것이 인상적이다.
def more_than_half(nums):
  half_check = {}

  if len(nums) < 2:
    return nums[0]
  else:
    count_nums = set(nums)
    for i in count_nums:
      half_check[i] = nums.count(i)
    max_key = max(half_check, key=half_check.get)
    return max_key

다른 답안 2

  • 이런 방법은 생각도 못했다... hashmap은 처음 본다.
  • collection에 대한 추가적인 공부가 필요해 보인다.
import collections

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

다른 답안 3

  • 빈 배열에 nums의 중복되지 않는 각 요소의 개수가 절반을 넘을 경우
  • 빈 배열에 추가하여 첫 번째 인덱스를 리턴한다.
  a = []
  for i in set(nums):
    if nums.count(i) > len(nums)/2:
      a.append(i)
  return a[0] 

🔖 참고 자료

(파이썬 공식 문서) collections — 컨테이너 데이터형

profile
(Backend Dev.) One step at a time

0개의 댓글