뒤죽박죽 코딩 이야기

2022년 2월 10일 목요일 - 으아아아악 첫월급!!!!

오늘 올려볼 문제는 560번 Subarray Sum Equals K 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

오늘은 조금 까다로워서 시행착오 한 3번정도 거쳤다..

입력

사진에서도 볼 수 있듯이 int 배열 1개와 int 1개가 주어진다.

풀이 및 코드

배열의 subarray의 합이 k와 같은 subarray가 몇개 있는지 구하는 문제이다.

처음에는 k에 대해서 생각하지 못하고 누적합의 차가 0인 경우만 생각했었다.

하지만 역시나 이는 제대로된 풀이가 아니었다.

그래서 다른 풀이를 생각해봤다.

일단 누적합마다 해쉬맵에 저장한다.

이 때 해쉬맵에 현재 누적합 - k 가 존재한다면 결과값에 해당 해쉬맵에 들어있는 값을 더한다.

이런식으로 시간복잡도 O(N)에 풀 수 있는 방법을 생각해냈다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int subarraySum(int[] nums, int k) {
        int sum = 0;
        int result = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

        map.put(0, 1);

        for(int i = 0; i < nums.length; i++)
        {
            sum += nums[i];

            if(!map.containsKey(sum))
                map.put(sum, 0);

            if(map.containsKey(sum - k))
            {
                result += map.get(sum - k);
            }

            map.put(sum, map.get(sum) + 1);
        }

        return result;
    }

}

제출 화면

오늘은 조금 까다로웠던 문제였다.

그래도 조금의 시행착오만으로 문제를 풀 수 있어서 다행인 것 같다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.