HashMap๐บ ์ ์ฌ์ฉํ๋ฉด ๋ฆฟ์ฝ๋์์ ๊ทธ๋๋ง ์ ์ผ ์ฝ๋ค๊ณ (?) ๋๊ปด์ง๋ Majority Elements ๋ฌธ์ ๋ฅผ ํ์ด๋ณด๊ฒ ๋ค!
์ฌ์ค ํด์ฌ๋งต์ ์ฌ์ฉํ๋ ๋ฌธ์ ๋ค์ ๋๋ถ๋ถ nested for loop ์ผ๋ก ํ ์ ์๊ฒ ์ง๋ง,
๋ด ๋ชฉํ๋ ๋ชจ๋ ๋ฌธ์ ์ Time Complexity๋ฅผ ์ต๋ํ O(n) ์ผ๋ก ๋ง๋ค๊ณ ์ถ๊ธฐ ๋๋ฌธ์ ํด์ฌ๋งต์ ์ฌ์ฉํ ์ฝ๋๋ฅผ ์จ๋ณด๋๋ก ํ๊ฒ ๋ค! ๐ค
"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๋ฒ์ผ๋ก ๋์ด๊ฐ๋ค.
"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
์คํ๋ ค ๋ ์ฌ์ด ์ฝ๋๋ผ ์ฝ๋ฉํธ๋ ์๋ตํ๊ฒ ๋ค ๐
๊ฒฐ๋ก ์ ํด์ฌ๋งต์ ์ฐ๋ฉด ์ฝ๋ ์ง๊ธฐ๊ฐ ํจ์ฌ ๋ ์์ํด์ง ๋ฟ๋๋ฌ, ์๊ฐ๋ณต์ก๋๋ ์ค์ด๋๋ ์ ์ธํฐ๋ทฐ์์ ๋งํ ๋ ํด์ฌ๋งต์ ์ฐ๋ผ๋ ๋ฐ์ด ์๊ฒผ๋์ง ๋์ฑ ์ ์๊ฒ๋์๋ค ๐คฃ