# ๐ป [LeetCode] Majority Element I, II - 169, 229

piscesfille01ยท2022๋ 6์ 8์ผ
0

## LEETCODE

๋ชฉ๋ก ๋ณด๊ธฐ
1/2

HashMap๐บ ์ ์ฌ์ฉํ๋ฉด ๋ฆฟ์ฝ๋์์ ๊ทธ๋๋ง ์ ์ผ ์ฝ๋ค๊ณ (?) ๋๊ปด์ง๋ Majority Elements ๋ฌธ์ ๋ฅผ ํ์ด๋ณด๊ฒ ๋ค!

์ฌ์ค ํด์ฌ๋งต์ ์ฌ์ฉํ๋ ๋ฌธ์ ๋ค์ ๋๋ถ๋ถ nested for loop ์ผ๋ก ํ ์ ์๊ฒ ์ง๋ง,
๋ด ๋ชฉํ๋ ๋ชจ๋  ๋ฌธ์ ์ Time Complexity๋ฅผ ์ต๋ํ O(n) ์ผ๋ก ๋ง๋ค๊ณ  ์ถ๊ธฐ ๋๋ฌธ์ ํด์ฌ๋งต์ ์ฌ์ฉํ ์ฝ๋๋ฅผ ์จ๋ณด๋๋ก ํ๊ฒ ๋ค! ๐ค

## ๐ฉ๐ปโ๐ป 169. Majority Element

"Given an array nums of size n, return the majority element."

๋ด๊ฐ ์๊ฐํ ์๊ณ ๋ฆฌ์ฆ์ ์ด๊ฑฐ๋ค.

• ๋งจ ์ฒ์ maximum ๊ฐ๊ณผ hash ๋์๋๋ฆฌ๋ฅผ initializing
• hash ์ key๋ฅผ nums ๋ด ์ซ์๋ก, value๋ฅผ corresponding number์ ๊ฐฏ์๋ก ์ง์ 
• ํด์ฌ๋งต์ด ์์ฑ๋๋ฉด, ๋งต ๋ด์ ๊ฐ์ผ๋ก loop์ ๋๋ฆฐ ๋ค hash[index] ๊ฐ n / 2 ๋ณด๋ค ํด ๋, ์ฒ์ initialize ํด๋์ maximum ๊ฐ์ ์ค์ 
• ๋ฃน์ด ๋๋๋ฉด maximum ๋ฆฌํด

๋ฐ๋ผ์ ์ฝ๋๋,

def majorityElement(nums: List[int]) -> int:
# initializing variables
maximum = 0
hash = {}

# making hash dictionary using enumerate() function
for i, v in enumerate(nums):
# index์ ํด๋นํ๋ ์ซ์์ count ์ธ์ i๊ฐ ๋๋  ๋ ๊น์ง dictionary update
hash[nums[i]] = 1 + hash.get(nums[i], 0)

# ํด์ฌ๋งต ๋ฃน ๋๋ฉด์
for j in hash:
# corresponding ํ๋ value๊ฐ ์กฐ๊ฑด ํ์ ์ด์์ด๋ฉด
if hash[j] > (len(nums) / 2):
# maximum์ j๋ก ์ค์ 
maximum = j

return maximum

์ ๋ง ๊ฐ๋จํ๋ค! ๐ถ
ํ๋ ์๊ธฐํ์๋ฉด, hash.get(nums[i],0) ๋ผ๊ณ  ์ด ์ด์ ๋ ํด์ฌ ์์์ ๋ด๊ฐ ์ฐพ๋ value ๊ฐ์ด ์์ ์๋ ์๊ธฐ ๋๋ฌธ์ ๋๋ฒ์งธ parameter์ default ๊ฐ์ธ 0์ ๋ฃ์ด์ฃผ์๋ค. (์ด๊ฑด ๋ด๊ฐ ๋์ค์ "์ ์ ๋ฌ์ง?" ์ถ์๊น๋ด ์ผ๋ฌ๋๋ ๊ฑฐ....)

๋น์ทํ ์ ํ์ ๋ฌธ์ ๋ฅผ ๋ ํ์ด๋ณด๊ณ  ์ถ์ด์ 229๋ฒ์ผ๋ก ๋์ด๊ฐ๋ค.

## ๐ฉ๐ปโ๐ป 229. Majority Element II

"Given an integer array of size n, find all elements that appear more than โ n/3 โ times."

๊ฐ์๊ธฐ Medium ์์ค์ ๋ฌธ์ ๊ฐ ๋์์ ์ด์ง ๊ฒ๋จน์์ง๋ง ๐ณ , ํด์ฌ๋ก ์ ํ์ด๋ณด์! ๋ผ๊ณ  ์๊ฐํ๊ณ  ๋ง๋ฌด๊ฐ๋ด๋ก ์๊ณ ๋ฆฌ์ฆ์ ์ง๋ณด์๋ค ๐จ (ใใใ...)

• ๋ฆฌํด ๊ฐ์ด ๋ฆฌ์คํธ์ด๊ธฐ ๋๋ฌธ์ ๋ฆฌํด ํ  ๋ฆฌ์คํธ์ ํด์ฌ๋งต initializing
• ์๊น์ ๋๊ฐ์ ๊ตฌ์กฐ๋ก hashmap ๋ง๋ค๊ธฐ
• hash loop ๋ด์์ hash[index]๊ฐ n / 3 ๋ณด๋ค ํฌ๋ฉด ์ฒ์ ๋ง๋  empty ๋ฆฌ์คํธ์ append
• loop ์ด ๋๋๋ฉด ๋ฆฌ์คํธ ๋ฆฌํด

์๊ณ ๋ฆฌ์ฆ ์ง๋ ๊ฑด ์ด ๋ฌธ์ ๊ฐ ๋ ์ฌ์ ๋ ๊ฒ ๊ฐ๋ค.

def majorityElement(nums: List[int]) -> List[int]:
allElementsList = []
hash = {}

for i, v in enumerate(nums):
hash[v] = 1 + hash.get(v, 0)

for j in hash:
if hash[j] > (len(nums) / 3):
allElementsList.append(j)
return allElementsList

์คํ๋ ค ๋ ์ฌ์ด ์ฝ๋๋ผ ์ฝ๋ฉํธ๋ ์๋ตํ๊ฒ ๋ค ๐

## ๐ ์ ๋ฆฌ

๊ฒฐ๋ก ์ ํด์ฌ๋งต์ ์ฐ๋ฉด ์ฝ๋ ์ง๊ธฐ๊ฐ ํจ์ฌ ๋ ์์ํด์ง ๋ฟ๋๋ฌ, ์๊ฐ๋ณต์ก๋๋ ์ค์ด๋๋ ์ ์ธํฐ๋ทฐ์์ ๋งํ ๋ ํด์ฌ๋งต์ ์ฐ๋ผ๋ ๋ฐ์ด ์๊ฒผ๋์ง ๋์ฑ ์ ์๊ฒ๋์๋ค ๐คฃ

I DO CODE!