๐Ÿ’ป [LeetCode] Majority Element I, II - 169, 229

piscesfille01ยท2022๋…„ 6์›” 8์ผ
0

LEETCODE

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

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

์˜คํžˆ๋ ค ๋” ์‰ฌ์šด ์ฝ”๋“œ๋ผ ์ฝ”๋ฉ˜ํŠธ๋Š” ์ƒ๋žตํ•˜๊ฒ ๋‹ค ๐Ÿ˜„


๐Ÿ“ ์ •๋ฆฌ

๊ฒฐ๋ก ์€ ํ•ด์‰ฌ๋งต์„ ์“ฐ๋ฉด ์ฝ”๋“œ ์งœ๊ธฐ๊ฐ€ ํ›จ์”ฌ ๋” ์ˆ˜์›”ํ•ด์งˆ ๋ฟ๋”๋Ÿฌ, ์‹œ๊ฐ„๋ณต์žก๋„๋„ ์ค„์–ด๋“œ๋‹ˆ ์™œ ์ธํ„ฐ๋ทฐ์—์„œ ๋ง‰ํž ๋•Œ ํ•ด์‰ฌ๋งต์„ ์“ฐ๋ผ๋Š” ๋ฐˆ์ด ์ƒ๊ฒผ๋Š”์ง€ ๋”์šฑ ์ž˜ ์•Œ๊ฒŒ๋˜์—ˆ๋‹ค ๐Ÿคฃ

profile
I DO CODE!

0๊ฐœ์˜ ๋Œ“๊ธ€