5 분 소요

Sliding Window

문제

문제 링크

Given an array of positive integers nums and a positive integer target, return the minimal length of a 

subarray

 whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4] Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1] Output: 0

Constraints:

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

스스로 고민

접근법

  • 배열에서 요소들의 합을 조합해서 타겟 넘버와 같거나 크면된다.
  • 요소의 합에 대한 제한은 없다
  • 만약 답이 없다면 리턴은 0
  • 답이 있다면 몇 개가 조합 되었는지 리턴하면 된다.
  • 조합은 가장 적은 숫자의 갯수로 이루어져야한다.

아는 패턴

  • Slide Window 를 활용하는 방법이 잘 떠오르지도 않고 감도 안잡혔다.
  • 기존에 했던 투 포인터와 해시맵을 이용해서 문제를 먼저 풀어보고 답이 나온다면 Slide Window 패턴을 활용할 방법이 생각날거라고 생각해서 일단 풀어봤다.

의사코드

  • 우선 배열을 정렬해준다. <- (문제를 틀리고 나서 보니 정렬해주면 안된다..😑)
  • 1차적으로 타겟 넘버가 배열에 있는지 확인한다. 있으면 1을 리턴
  • 배열에 숫자가 한 개만 있으며 타겟넘버와 같다면 1개 리턴
  • 비어있는 배열일 경우 0 리턴
  • 해시맵과 반복문으로 2개의 조합만으로 답이 있는지 찾는다.
  • 반복문이 끝났다면 해시맵이 완성되어 있으므로 해당 해시맵으로 3개 조합 4개 조합 이런식으로 찾는다.
    • 예를 들어 만들어진 해시맵의 가장 작은 값과 가장 큰 값의 합은 어차피 타겟 값을 못 넘고 문제 자체가 어차피 같거나 크기만 하면 되니까 가장 큰 수를 순서대로 더해주면 된다.

구현 코드

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        nums.sort()
        if target in nums:
            return 1
        if sum(nums) == target:
            return len(nums)
        if len(nums) < 2:
            return 0
        num_dict = {}

        for i, num in enumerate(nums):
            complement = target - num
            if num >= complement or complement in num_dict:
                return 2
            num_dict[i] = num

        last_key = list(num_dict.keys())[-1]

        new_target = num_dict[last_key-1] + num_dict[last_key]
        count = 3
        for i in range(last_key-2, 0, -1):
            if new_target + num_dict[i] >= target:
                return count
            else: 
                count +=1
                new_target += num_dict[i]

        return 0
  • 틀렸다..
  • 문제 내에서 연속된 말이 따로 없어서 정렬부터 하고 문제를 풀었는데 뭔가 이상했다. [12,28,83,4,25,26,25,2,25,25,25,12] , target = 213 일 경우 답이 8로 나왔다 답은 83, 28, 26, 25, 25, 25, 25 이렇게 만 합하면 213을 넘으니 7개가 답인거 같은데 …
    • 문제에 파란색 글씨로 subarray 가 있어서 설마…하고 클릭해 보니 A subarray is a contiguous non-empty sequence of elements within an array. 라고 나온다 😑
  • 처음 문제를 봤을 때 Window Slide 패턴을 어떻게 적용해야 될 지 감이 안잡혔는데 그래도 틀린 덕분에 어떻게 패턴을 적용해야될지 감이 잡혔다.
class Solution:

    def minSubArrayLen(self, target: int, nums: List[int]) -> int:

        for i in range(len(nums)):

            for r in range(len(nums)):

                if sum(nums[r:r+i+1]) >= target:

                    return i+1

        return 0
  • 시간 초과됨
class Solution:

    def minSubArrayLen(self, target: int, nums: List[int]) -> int:

        total = 0
        count = 1
        length = len(nums)
        

        while total != length + 1:

            for i in range(length+1):

                if i + count > length:

                    pass

                else:

                    if sum(nums[i:i + count]) >= target:

                        return count

                    if count == length:

                        count = 1

            count += 1

            total += 1

  

        return 0
  • 답은 정확히 나오는거 같은데 계속 시간초과가 나온다.
  • while 이랑 for를 각 각 한 번씩 사용해서 O(n^2) 인줄 알았는데 sum 연산도 들어가면 O(n^3) 이 될 수 있다고 한다.
  • 반복문을 어떻게 줄일 수 있는지 곰곰히 생각해봤다.

최종 의사코드

sum 에대해서 매번 실행되는걸 줄일라면 window slide를 넓히거나 좁힐 때만 값을 변경해 주는 식으로 해줘야함

  • 배열의 길이 선언
  • 처음 시작표시 변수 선언
  • 뽑아낸 배열의 최소 크기
  • 현재 뽑아낸 배열 원소의 합
  • 반복문을 통해 오른쪽 값을 하나 씩 합산
  • 합산할 때 마다 타겟 값을 넘는지 체크
  • 타겟 값보다 현재의 합산 값이 더 많다면 while 문 실행
  • 연속된 배열에서 필요없는 부분들을 쏙 빼야되니까 이제 왼쪽부터 하나씩 제거
  • 이전보다 더 작은 최소배열크기를 반환
  • 마지막에 최소배열크기가 n+1 (나올 수 없는 값)이면 0으로 반환 아니면 업데이트된 최소 배열크기 반환

최종 구현코드

class Solution:

    def minSubArrayLen(self, target: int, nums: List[int]) -> int:

        n = len(nums)

        left = 0

        length = n + 1

        current_sum = 0

        for right in range(n):

            current_sum += nums[right]

            while current_sum >= target:

                length = min(length, right - left + 1)

                current_sum -= nums[left]

                left += 1

        return length if length != n + 1 else 0

시간 복잡도와 공간 복잡도

  • 시간 복잡도: 주어진 배열의 길이를 n이라고 할 때, 코드는 한 번의 배열 순회를 수행하며, 각 위치에서 최대 한 번의 연산을 수행한다. 따라서 시간 복잡도는 O(n) 이다. 내부의 while 루프가 한 번에 최대 n번 돌기 때문에 연산이 총 O(n)번 실행된다.

  • 공간 복잡도: 추가적인 공간을 사용하지 않고 주어진 배열 내에서만 변수를 조작하므로, 공간 복잡도는 O(1) 다. 입력 배열 외에는 상수 개의 변수만 사용하므로 추가적인 공간을 할당하지 않는다.

회고 과정

  • 우선 문제를 정확히 보는게 제일 중요한거 같다. 근데 한국어로 쓰여 있어도 문제가 너무 길면 잘 파악이 안된다.
  • 그래서 그냥 무지성으로 풀어보고 틀릴 때 마다 고치면서 교집합을 만들어서 해결하는 방법도 좋은 거 같다.

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if sum(nums) < target: return 0

        s, l, count = 0, 0, len(nums)
        for r, val in enumerate(nums):
            s += val
            while s >= target:
                s -= nums[l]
                count = min(count, r - l + 1)
                l += 1
                
        return count
  • 정말 신기하게도 다른 코드들 모두 논리는 비슷하게 풀어내는거 같다. 다만 다른 사람 코드를 보면서 같은 논리여도 어떻게 쓰느냐에 따라 가독성이 많이 달라지는거 같다.
  • 가독성, 소흘히 하지 말자

댓글남기기

참고