Python: Code Taka 2주차 2

Q. 숫자로 이루어진 배열인 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개라고 가정한다.)

나의 답

def more_than_half(nums):
  c = int(len(nums) / 2) + 1
  for i in nums:
    if nums.count(i) >= c:
      return i

1. 파라미터로 들어오는 숫자 배열의 길이를 2로 나눈 후 +1을 하여 과반수의 기준을 만든다.
2. 반복문으로 count 메서드를 활용하여 각 숫자가 배열에서 몇 개 존재하는지 알아낸 후, 그 숫자가 과반수 이상이면 해당 숫자를 리턴한다.

지금 다시 보니, 반복문에서 같은 숫자를 count 하고 있어 효율이 좋지 않다. 예를 들면 1이라는 숫자가 얼마나 반복되는지 count 한 후에, 다시 1이라는 숫자를 count 한다.
또한 과반수가 넘는 숫자가 여러 개 있다고 가정한다면 이와 같은 답은 재사용될 수 없다.

아래의 답은 배열의 길의 과반수가 넘는 숫자가 하나만 존재한다고 가정했을 때의 답이다.

수정한 답

def more_than_half(nums):
    majority = int(len(nums) / 2) + 1
    num = None
    
    for i in nums:
        if num == i:
            continue
            
        if nums.count(i) >= majority:
            return i
        else:
            num = i
    
    return num

num 이라는 변수를 선언하여 이미 체크했던 숫자를 저장해놓아, 같은 연산을 반복하지 않도록 하였다. 만약 [1, 1, 1, 2, 2, 2, 2] 라는 숫자 배열이 들어온다면 1을 한 번 체크하고 그 다음 1과 1은 체크하지 않고 넘어가게 하여, 반복문이 도는 횟수를 줄일 수 있었다.

솔루션 (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]

sort 를 이용한 답은 아이디어..