[Top Interview Questions] 169. Majority Element

정답)

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count, res = 1, nums[0]

        for i in range(1, len(nums)):
            if nums[i] == res:
                count += 1
            else:
                if count == 0:
                    res = nums[i]
                    count += 1
                else:
                    count -= 1

        return res

문제)

문제출처

 

n개의 원소가 있는 배열 nums가 주어졌을 때 nums의 과반수 원소를 리턴하시오.

 

과반수 원소란 nums에 n / 2번 보다 더 많이 존재하는 원소를 가리킵니다.

nums에는 항상 과반수 원소가 존재합니다.

 

예시 1)

nums = [3, 2, 3]

output = 3

 

예시 2)

nums = [2, 2, 1, 1, 1, 2, 2]

output = 2

 

제한)

n == nums의 길이

1 <= n <= 50000

-1000000000 <= nums[i] <= 1000000000

 

도전)

O(n)의 시간 복잡도와 O(1)의 공간 복잡도를 문제를 푸시오.

풀이)

nums의 0번째 원소를 변수 res에 저장합니다.

nums를 선형 하면서 res와 같은 값을 발견하면 개수를 세어줄 count변수도 만듭니다.

 

선형 중 res와 같은 값이 발견되면 count에 1을 더합니다.

다른 값이 발견되면 count에 1을 빼줍니다.

 

만약 count가 0이 된 상태에서 다른 원소를 발견하면 res에 발견된 다른 원소를 저장해 줍니다.

선형이 완료되면 res에는 과반수 원소가 저장되어 있습니다.

 

def majorityElement(self, nums: List[int]) -> int:
        count, res 변수

        만약 nums[i]가 res와 같다면:
            count += 1
        
        만약 nums[i]가 res와 같지 않다면:
            count가 0이라면:
                res = nums[i]
                count += 1
            count가 0이 아니라면:
                count -= 1
        
        res를 리턴

초기세팅)

nums의 길이가 항상 1보다 크거나 작다고 했으니 nums의 0번째 원소를 저장해 줍시다.

 

고로 count는 1, res는 nums[0]이 되겠습니다.

 

def majorityElement(self, nums: List[int]) -> int:
        count, res = 1, nums[0]

for 문)

0번째 원소는 확인했으니 1번째 원소부터 확인해 줍시다.

 

만약 nums[i]가 res와 같다면 count를 1 더해줍시다.

 

만약 nums[i]가 res와 다르다면 2가지의 경우가 존재합니다.

1. count가 0이라서 res를 업데이트해줘야 되는 경우

2. count가 아직 0보다 커서 count만 1을 빼주는 경우

 

고로 각 상황에 맞게

res를 업데이트해주면 count도 1 더해주고

res를 업데이트 안 해줘도 되는 경우에는 count에 1을 빼주기만 합니다.

 

nums의 선형이 끝나면 res를 리턴합니다.

 

def majorityElement(self, nums: List[int]) -> int:
        count, res = 1, nums[0]

        for i in range(1, len(nums)):
            if nums[i] == res:
                count += 1
            else:
                if count == 0:
                    res = nums[i]
                    count += 1
                else:
                    count -= 1

        return res

디버깅)

nums = [2, 2, 1, 3, 1, 2, 2]

 

count = 1

res = 2

 

(i = 1)

count = 2

 

(i = 3)

count = 1

 

(i = 4)

count = 0

 

(i = 5)

res = 1

count = 1

 

(i = 6)

count = 0

 

(i = 7)

res = 2

count = 1

 

 

제가 처음에 이 문제를 풀었을 때는 너무 복잡하게 생각했던 것 같습니다. 과반수 원소가 n/2보다 많이 나온다는 사실에 집중했다면 이렇게 단순하게 풀었을 텐데 말이죠. 단순하게 크게 크게 볼 줄 알아야 되는 거 같습니다. 그리고 복습도 굉장히 중요하고요. 

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)