[LeetCode] 169. Majority Element

안녕하세요

 

오늘은 LeetCode의 169. Majority Element 문제를 풀어보겠습니다.

 

 

이 문제는 주어진 배열에서 과반수 이상의 빈도로 나타나는 요소를 찾는 문제였습니다. 문제 조건으로는 O(n) 의 시간 복잡도, O(1)의 공간 복잡도 안에서 문제를 해결해보는 것이었습니다. 

 

제가 작성한 코드는 다음과 같습니다. 먼저 candidate는 정답이 될 수 있는 배열 내의 요소이고, count 는 해당 요소가 나타난 횟수 입니다. for 문을 통해 배열을 돌며 후보와 카운트를 업데이트했습니다.

 

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        
        candidate = None    # 후보 요소
        count = 0   # 후보 요소 출현 횟수

        for i in nums:
            if count == 0:
                candidate = i   # 배열을 순회하며 후보 업데이트
            if i == candidate:
                count += 1  # 후보 요소가 등장한 횟수 카운트
            else:
                count -= 1

        return candidate

 

다른 사람들의 솔루션을 보다가 인상깊은 코드를 발견했습니다.

 

이 코드였는데요. 매우 간결하고 직관적이라 인상깊었습니다. 모든 배열의 요소를 크기 순으로 나열한 후, 중앙값을 출력하는 방식이었습니다. 문제의 정답에 해당하는 요소가 반드시 존재한다는 가정이 있었으므로 합리적인 풀이 방법인 것은 확실하다고 생각합니다. 시간은 더 걸리는 알고리즘이었습니다만 저는 이 분의 문제 접근 방식을 배우고 싶었습니다. 창의적이고 다양한 문제 접근 방식을 고민해봐야할 것 같습니다!