๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์•Œ๊ณ ๋ฆฌ์ฆ˜/LEETCODE

Majority Element | LeetCode 824 | Python3 ๐Ÿ

๋ฐ˜์‘ํ˜•

 

๐Ÿ“„ ๋ชฉ์ฐจ

     

     

    ๐Ÿค” ๋ฌธ์ œ : Majority Element | LeetCode 824

    ๋ฌธ์ œ: https://leetcode.com/explore/interview/card/top-interview-questions-medium/114/others/824/

     

    ์ฃผ์–ด์ง„ ๋ฐฐ์—ด์—์„œ ์ ˆ๋ฐ˜ ์ด์ƒ์„ ์ฐจ์ง€ํ•˜๋Š” ์›์†Œ๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

    ๋‹จ,  Could you solve the problem in linear time and in O(1) space?

     

     

    ๐Ÿ’ก ํ’€์ด

    1. Majoirity Component๋Š” ๋‹ค๋ฅธ ์›์†Œ ๋‹ค ํ•ฉ์นœ๊ฑฐ๋ณด๋‹ค ๋” ๋งŽ์ด ๋‚˜์˜จ๋‹ค๋Š” ์ !

    ๊ทธ๋ƒฅ dictionary ์ด์šฉํ•ด์„œ ๊ฐ ์›์†Œ๋ณ„ ๋‚˜์˜จ ํšŸ์ˆ˜ countํ•˜๋Š” ๊ฑธ๋กœ๋Š” ๋„์ €ํžˆ O(1) space๋งŒ์— ํ•ด๊ฒฐ์ด ์•ˆ ๋˜์–ด discussion์„ ๋ดค์Šต๋‹ˆ๋‹ค.. ใ…Ž

     

    ํ•ต์‹ฌ์€ Majoirity Component๋Š” ๋‹ค๋ฅธ ์›์†Œ ๋‹ค ํ•ฉ์นœ๊ฑฐ๋ณด๋‹ค ๋” ๋งŽ์ด ๋‚˜์˜จ๋‹ค๋Š” ์ ์ž…๋‹ˆ๋‹ค.

    Majoirty component๊ฐ€ ๋‚˜์˜ค๋ฉด +1, ๋‹ค๋ฅธ๊ฒŒ ๋‚˜์˜ค๋ฉด -1์„ ํ•˜๋ฉด ๋งˆ์ง€๋ง‰์—๋Š” ๋ฌด์กฐ๊ฑด count๊ฐ€ ์–‘์ˆ˜์—ฌ์•ผ ํ•œ๋‹ค๋Š” ์ ์ด์ฃ .

     

    from typing import List
    class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            candidate, count = None, 0
            for i in nums:
                if count == 0 :
                    candidate = i
                    count = 1
                else:
                    if i == candidate : count += 1
                    else: count -= 1
            return candidateโ€‹

     

    ์•„๋ž˜๋Š” ์˜ˆ์‹œ input์ž…๋‹ˆ๋‹ค. 

    input 2 3 3
    candidate 2 2 3
    count 1 0 1

    ๋‹ค๋ฅธ candidate์œผ๋กœ ์‹œ์ž‘ํ–ˆ๋‹ค๊ฐ€๋„ ๊ฒฐ๊ตญ 3์œผ๋กœ ์„ธํŒ…๋จ

     

    input 3 2 3 4 3
    candidate 3 3 3 3 3
    count 1 0 1 0 1

    ์ค‘๊ฐ„์— ๋‹ค๋ฅธ element๊ฐ€ ๋ผ์–ด์žˆ๋”๋ผ๋„ ๊ฒฐ๊ตญ 3์ด ๋จ

     

    input 3 4 4 3 3
    candidate 3 3 4 4 3
    count 1 0 1 0 1

    ์ค‘๊ฐ„์— candidate์ด ๋ฐ”๋€Œ์—ˆ๋‹ค๊ฐ€๋„ ๊ฒฐ๊ตญ 3์œผ๋กœ ๋Œ์•„์˜ด

    ๋ฐ˜์‘ํ˜•