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
- 파라미터로 들어오는 숫자 배열의 길이를 2로 나눈 후 +1을 하여 과반수의 기준을 만든다.
- 반복문으로 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 를 이용한 답은 아이디어..
Author And Source
이 문제에 관하여(Python: Code Taka 2주차 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pm1100tm/Python-CodeTaka-8일차저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)