Published:
Updated:

  • Reference
  • ์ฒซ๋ฒˆ์งธ ์ ‘๊ทผํ–ˆ๋˜ ๋ฐฉ์‹์€ ์“ฐ๋ ˆ๊ธฐ๋ผ๊ณ  ์จ๋†“์€ ๋งŒํผ ๋…ผ๋ฆฌ์  ์˜ค๋ฅ˜๊ฐ€ ์—„์ฒญ๋‚œ ๋ฐฉ์‹์ด์—ˆ๋‹ค.
  • ๋‘๋ฒˆ์งธ ๋ฐฉ์‹์€ ๋ฐ˜๋ณต๋ฌธ์„ ๋Œ๋ฉด์„œ i-1๋ฒˆ์งธ์™€ i๋ฒˆ์งธ์— ๋”ฐ๋ผ cnt๋ฅผ ์ฆ๊ฐ€ํ•˜๊ณ  ๋ง๊ณ  ๋“ฑ๋“ฑ ์—„์ฒญ ๋ณต์žกํ•˜๊ฒŒ ์ƒ๊ฐํ•˜๋ฉด์„œ ํ’€์–ด๋ดค๋Š”๋ฐ ๋„์ €ํžˆ ํ’€๋ฆฌ์งˆ ์•Š์•˜๋‹ค.
  • ๋ฆฟ์ฝ”๋“œ ๋„์›€์œผ๋กœ xor (๋น„ํŠธ ์—ฐ์‚ฐ์ž)๋กœ 2๊ฐœ๊ฐ€ ๋™์ผํ•˜๋ฉด ๊ณ„์‚ฐ์ด ๋˜๊ฒŒ๋”ํ•˜๋Š” ์•„์ด๋””์–ด๋ฅผ ์•Œ ์ˆ˜ ์žˆ์—ˆ๋‹ค.
  • Runtime 137 ms
  • Beats 66.26%
  • ์‹œ๊ฐ„๋ณต์žก๋„: $O(N)$


Solution

from typing import List


class Solution:
    # ๋น„์–ด ์žˆ์ง€ ์•Š์€ ์ •์ˆ˜ ๋ฐฐ์—ด์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ํ•œ ๊ฐœ๋ฅผ ์ œ์™ธํ•œ ๋ชจ๋“  ์š”์†Œ๊ฐ€ ๋‘ ๋ฒˆ ๋‚˜ํƒ€๋‚จ
    # ๊ทธ ์ œ์™ธ๋œ ํ•œ ๊ฐœ์˜ ์š”์†Œ๊ฐ€ ๋ฌด์—‡์ธ์ง€ ์ฐพ์ž!
    # linear runtime complexity: O(N) ์‹œ๊ฐ„ ๋ณต์žก๋„
    def singleNumber(self, nums: List[int]) -> int:
        # ์“ฐ๋ ˆ๊ธฐ
        # nums.sort()
        # # ์ •๋ ฌํ•˜๋ฉด ๋‹ต์€ nums[len(nums) - 1] or nums[0]
        # if len(nums) > 1:
        #     if nums[0] == nums[1]:
        #         return nums[len(nums) - 1]
        #     if nums[len(nums) - 1] == nums[len(nums) - 2]:
        #         return nums[0]
        # else:  # Example 3๊ณผ ๊ฐ™์€ ์ƒํ™ฉ
        #     return nums[0]

        # i-1๊ณผ i๋ฅผ ๊ณ„์† ๋Œ๋ฉด์„œ cnt๋ฅผ ์ฆ๊ฐ€์‹œ์ผœ๋ณผ๊นŒ..? -> X
        # ์œ„์ฒ˜๋Ÿผ ์“ฐ์ง€ ๋ง๊ณ  XOR ๋น„ํŠธ ์—ฐ์‚ฐ์ž ์‚ฌ์šฉํ•˜์ž
        # 2๊ฐœ๊ฐ€ ๊ฐ™์„ ๋•Œ ์ฒดํฌ๋˜๋Š” ์•„์ด๋””์–ด๋กœ!
        answer = 0
        for i in nums:
            answer ^= i

        return answer

print(Solution().singleNumber([2, 2, 1]))
print(Solution().singleNumber([4, 1, 2, 1, 2]))
print(Solution().singleNumber([1]))

# Expected: 354
print(Solution().singleNumber(
    [-336, 513, -560, -481, -174, 101, -997, 40, -527, -784, -283, -336, 513, -560, -481, -174, 101, -997, 40, -527,
     -784, -283, 354]))

Leave a comment