💻 [LeetCode] Majority Element I, II - 169, 229

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

오히려 더 쉬운 코드라 코멘트는 생략하겠다 😄

---

📍 정리

결론은 해쉬맵을 쓰면 코드 짜기가 훨씬 더 수월해질 뿐더러, 시간복잡도도 줄어드니 왜 인터뷰에서 막힐 때 해쉬맵을 쓰라는 밈이 생겼는지 더욱 잘 알게되었다 🤣