problem 1.9

main.py

"""
## 문제 : 배열에서 다수의 요소 찾기

- 정수형 배열이 주어졌을 때, 다수의 요소를 찾아보자.
- 다수의 요소는 배열 내에서 [n / 2] 번 (floor(n / 2))를 초과하여 나타나는 요소를 말한다.
- 예를 들어서, 배열 요소의 총 개수가 9개라면, n / 2는 4.5이다. 결국에 5번 이상 나타나는 요소를 찾으면 된다.
- 배열은 항상 1개 이상의 요소를 가지고 있으며, 다수의 수가 무조건 하나 존재 한다고 가정하자.

## 제한사항 :
- 정수형 배열이 주어진다.
- 최소한 1개 이상의 요소를 가지고 있으며, 다수의 수가 무조건 배열 내에서 존재한다.

## 아이디어 :
- 순회를 하면서, 빈도를 저장한다.
## 구현

## 테스트
"""
from math import floor
from typing import List


def solve(elements: List[int]) -> List[int]:
    target_dict = {}
    length = len(elements)

    nth = floor(length / 2)

    for elem in elements:
        if not target_dict.get(f'{elem}'):
            target_dict[f'{elem}'] = 1
        else:
            target_dict[f'{elem}'] += 1

    result = []

    for k, v in target_dict.items():
        if v > nth:
            result.append(k)
    return result


if __name__ == '__main__':
    input_list = list(map(int, input().split()))
    print(solve(input_list))

from typing import List

# 이중 반복문을 통해서 값을 알아내었다.
def majorityElement(nums: List[int]) -> int:
    majority_count = int(len(nums) / 2)

    for i, item_i in enumerate(nums):
        count = 0
        for j, item_j in enumerate(nums[i:], start=i)
            if item_i == item_j:
                count += 1
            if count > majority_count:
                return item_i
    return -1

# 해시 맵을 이용하는 방법
def majorityElement2(nums: List[int]) -> int:
    majority_count = int(len(nums) / 2)

    hashmap = {}

    for num in nums:
        if hashmap.get(num) is not None:
            hashmap[num] = hashmap[num] + 1
        else:
            hashmap[num] = 1

        if hashmap[num] > majority_count:
            return num

    return -1

# 정렬을 통한 값을 알아내는 방법
def majorityElement3(nums: List[int]) -> int:
    return sorted(nums)[int(len(nums) / 2)]