class Solution:
def majorityElement(self, nums: List[int]) -> int:
std = len(nums) / 2
_map = {}
for i in nums:
try:
_map[i]
except KeyError:
_map[i] = 0
finally:
_map[i] += 1
if _map[i] > std:
return i
- 파이썬 스타일 가이드에 따라 가독성, 명확성, 간결성 있게 코드를 작성해보았다.
from collections import defaultdict 를 사용하면, 특정 타입에 대한 dict를 초기화할 수 있는데 KeyError를 방지할 수 있다.
class Solution:
def majorityElement(self, nums: List[int]) -> int:
from collections import defaultdict
std = len(nums) / 2
_map = defaultdict(int)
for i in nums:
_map[i] += 1
if _map[i] > std:
return i
- 일반적인 코드 같지만, 난 뭔가 위에가 더 좋다.
- 성능은 비슷하다.
list에 count() 내장 함수를 사용하면 동일한 값의 개수를 리턴합니다.
class Solution:
def majorityElement(self, nums: List[int]) -> int:
std = len(nums) / 2
map_ = {}
for i in nums:
if not i in map_:
map_[i] = nums.count(i)
if map_[i] > std:
return i
파이썬 스타일 가이드에서는 명령형보다는 선언형으로 코드로 작성하는 것을 권장합니다.
class Solution:
def majorityElement(self, nums: List[int]) -> int:
from collections import Counter
std = len(nums) / 2
map_ = dict(Counter(nums))
# return [k for k, v in map_.items() if v > std][0]
return next(filter(lambda x: map_[x] > std, map_))
- Counter 를 사용하면 Counter({3: 2, 2: 1})의 결과를 얻을 수 있는데 dict() 로 감싸면 일반적인 dict 가 된다.
- 명령형 vs. 선언형 차이를 예시로 들면,
- map_ = {} 초기화 후, loop 를 돌면서 map_ 의 값을 채워주는 것이 명령형.
- map_ = dict(Counter(nums)) 처럼 map_ 은 {3: 2, 2: 1} 이라고 선언하는 게 선언형.
Follow-up: Could you solve the problem in linear time and in O(1) space?
풀이를 보니 Moore's Voting 알고리즘을 사용하면 공간복잡도 O(1)로 문제를 풀 수 있다고 한다.
class Solution:
def majorityElement(self, nums: List[int]) -> int:
cnt, cur = 0, 0
for num in nums:
if cnt == 0:
cur = num
cnt = 1
elif cur == num:
cnt += 1
else:
cnt -= 1
return cur
'LeetCode' 카테고리의 다른 글
704, Binary Search (0) | 2024.05.23 |
---|---|
235, Lowest Common Ancestor of a Binary Search Tree (0) | 2024.02.25 |
217, Contains Duplicate (0) | 2024.02.19 |