[ํŒŒ์ด์ฌ] LeetCode 560. Subarray Sum Equals K ๐Ÿ‘‰๐Ÿป ๊ตฌ๊ฐ„ ํ•ฉ / Prefix Sum

Youngeui Hongยท2023๋…„ 10์›” 25์ผ
0

์•Œ๊ณ ๋ฆฌ์ฆ˜

๋ชฉ๋ก ๋ณด๊ธฐ
9/12

๐Ÿ‘€ ๊ตฌ๊ฐ„ ํ•ฉ ๋ฌธ์ œ

์—ฐ์†์ ์œผ๋กœ ๋‚˜์—ด๋œ N๊ฐœ์˜ ์ˆ˜๊ฐ€ ์žˆ์„ ๋•Œ ํŠน์ • ๊ตฌ๊ฐ„์˜ ๋ชจ๋“  ์ˆ˜๋ฅผ ํ•ฉํ•œ ๊ฐ’์„ ๊ณ„์‚ฐํ•˜๋Š” ๋ฌธ์ œ

๐Ÿ’ก Prefix Sum

Prefix Sum์€ ๋ฐฐ์—ด์˜ ๋งจ ์•ž๋ถ€ํ„ฐ ํŠน์ • ์œ„์น˜๊นŒ์ง€์˜ ํ•ฉ์„ ๋ฏธ๋ฆฌ ๊ตฌํ•ด ๋†“์€ ๊ฒƒ์„ ์˜๋ฏธํ•œ๋‹ค.

์ด Prefix Sum์„ ํ™œ์šฉํ•˜๋ฉด ๊ตฌ๊ฐ„ ํ•ฉ์„ ์‰ฝ๊ฒŒ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด ๋ฐฐ์—ด์˜ Left๋ฒˆ์งธ ์›์†Œ๋ถ€ํ„ฐ Right๋ฒˆ์งธ ์›์†Œ๊นŒ์ง€ ๋”ํ•œ ๊ฐ’์€ Prefix Sum์˜ ๋ฐฐ์—ด P์˜ Right๋ฒˆ์งธ ์›์†Œ ๊ฐ’์—์„œ Left - 1 ์›์†Œ ๊ฐ’์„ ๋บ€ ๊ฐ’์ด๋‹ค.

๐Ÿ‘ฉ๐Ÿปโ€๐Ÿ’ป LeetCode 560 ๋‹ต์•ˆ

LeetCode 560๋ฒˆ ๋ฌธ์ œ๋Š” ๋ฐฐ์—ด์˜ ํŠน์ • ๊ตฌ๊ฐ„์˜ ํ•ฉ์ด k๊ฐ€ ๋˜๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค.

์ด ๋ฌธ์ œ๋Š” prefix sum ๊ฐœ๋…๊ณผ dictionary๋ฅผ ํ™œ์šฉํ•ด์„œ ํ’€ ์ˆ˜ ์žˆ๋‹ค.

class Solution(object):
    def subarraySum(self, nums, k):
        result = 0 # ๊ฐ€๋Šฅํ•œ ๊ฒฝ์šฐ์˜ ์ˆ˜
        prefix_sum = 0 # ๋ˆ„์  ํ•ฉ
        d = {0: 1} # ๋ˆ„์  ํ•ฉ์˜ dictionary

        for i in nums:
            prefix_sum = prefix_sum + i

            # (ํ˜„์žฌ๊นŒ์ง€์˜ ๋ˆ„์ ํ•ฉ prefix_sum - ๋ชฉํ‘œ๊ฐ’ k)๊ฐ€ ๋ˆ„์  ํ•ฉ dictionary์— ์žˆ๋‹ค๋ฉด 
            # ๋ชฉํ‘œ๊ฐ’ k๋ฅผ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๊ตฌ๊ฐ„์ด ์กด์žฌํ•œ๋‹ค๋Š” ๊ฒƒ
            # ๊ฐ€๋Šฅํ•˜ ๊ฒฝ์šฐ์˜ ์ˆ˜์— d[prefix_sum - k]๋งŒํผ์„ ์ถ”๊ฐ€
            if prefix_sum - k in d:
                result = result + d[prefix_sum - k]

            # ๋”•์…”๋„ˆ๋ฆฌ์˜ ๊ฐ’ ์ฑ„์›Œ ๋„ฃ๊ธฐ
            if prefix_sum not in d:
                d[prefix_sum] = 1
            else:
                d[prefix_sum] = d[prefix_sum] + 1

        return result

0๊ฐœ์˜ ๋Œ“๊ธ€