준호씨의 블로그

hackerrank - Migratory Birds - Python3 본문

개발이야기/PS - Problem Solving, 알고리즘

hackerrank - Migratory Birds - Python3

준호씨 2020. 5. 29. 23:54
반응형

문제: https://www.hackerrank.com/challenges/migratory-birds/problem

대륙간 이동을 하는 새들의 인구에 대한 연구를 요청받았습니다. 관심 있는 조류의 각 유형은 정수 값으로 식별됩니다. 특정 종류의 새가 발견될 때마다 ID 번호가 배열에 추가됩니다. 목격 목록이 주어지면 어떤 종류의 새가 가장 보편적인지 알아내고 싶습니다. 당신의 임무는 해당 조류의 유형 번호를 인쇄하고 둘 이상의 유형의 조류가 동일하게 공통인 경우 가장 작은 ID 번호를 가진 유형을 선택하십시오.

예를 들어, arr=[1,1,2,2,3] 형식의 조류 관찰이 있습니다. 1과 2 유형이 각각 두 번, 3 유형이 한번 있습니다. 두 번 보인 두 타입 중 작은 숫자를 고릅니다. 유형 1입니다.

Function Description

migratoryBirds함수를 완성하시오. 가장 자주 보인 조류 중 낮은 숫자를 반환합니다.

Input Format

  • 5 <= n <= 2x10^5
  • 타입은 1,2,3,4,5

Output Format

가장 흔한 유형 번호를 출력하시오. 만약 동일 빈도가 두 개 이상이면 가장 작은 ID 번호를 선택합니다.

Sample Input 0

6
1 4 4 4 5 3

Sample Output 0

4

Explanation 0

  • 유형 1: 새 1마리
  • 유형 2: 새 0마리
  • 유형 3: 새 1마리
  • 유형 4: 새 3마리
  • 유형 5: 새 1마리

자주 출몰한 새의 유형은 4입니다. 답은 4입니다.

풀이

템플릿 코드

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the migratoryBirds function below.
def migratoryBirds(arr):

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    arr_count = int(input().strip())

    arr = list(map(int, input().rstrip().split()))

    result = migratoryBirds(arr)

    fptr.write(str(result) + '\n')

    fptr.close()

 

일단 가장 흔한 유형을 찾아야 합니다. collections에 있는 Counter를 사용하면 간단히 찾을 수 있습니다.

from collections import Counter

arr = [1, 4, 4, 4, 5, 3]
print(Counter(arr).most_common())

결과는

[(4, 3), (1, 1), (5, 1), (3, 1)]

이 나옵니다. 카운트를 센 다음 가장 많은 순으로 정렬한 것입니다.

이제 가장 많이 등장한 것들 중 유형 숫자가 가장 작은 것을 찾으면 됩니다.

from collections import Counter

# Complete the migratoryBirds function below.
def migratoryBirds(arr):
    most_commons = Counter(arr).most_common()

    max_frequencies = most_commons[0][1]

    answer = 5
    for common in most_commons:
        if common[1] != max_frequencies:
            break
        answer = min(answer, common[0])
    return answer

 

반응형
Comments