[파이썬/Python] Leet Code 1493(Medium): Longest Subarray of 1's After Deleting One Element

숨·2025년 8월 24일

코테

알고리즘 문제 풀이

목록 보기

119/128

📌 문제 : Leet Code 1493

📌 문제 탐색하기

nums : 입력되는 배열 ( $1 ≤ nums.length ≤ 10^5$ )

문제 풀이

이진수가 담긴 배열 array에서 1개의 요소를 반드시 삭제해야 할 때 오직 1만 있는 가장 길고 빈칸이 없는 Substring의 크기를 반환하는 문제이다.

배열 전체를 확인하면서 1로 연속된 부분 배열의 최장 길이를 빠르게 찾아야 한다.
→ 슬라이딩 윈도우 활용

📖 슬라이딩 윈도우

배열에서 연속된 부분을 효율적으로 다루는 방법

진행 과정

2개의 포인터(left, right)로 구간 정하기

조건 따라 윈도우 사이즈 확장 또는 축소

사용 경우

$O(n^2)$ 에 해당하는 중첩 루프 → $O(n)$ 하나의 루프로 최적화할 때 많이 사용

최대(최소) 합 가진 부분 합, 길이 k의 구간, 연속된 1/0의 최대 길이 등

연속이란 조건이 있다면 높은 확률로 사용 가능

구현

right가 배열 순회하면서 오른쪽 포인터 역할
만나는 값이 0이면 0의 개수 +1
해당 윈도우 내에서 0의 개수가 2 이상이면
- left 포인터 움직
- 윈도우 내 0의 개수를 1 이하로 유지
매 순간 최대 윈도우(구간) 크기 계산해 갱신
반복 끝나면 최장 길이 반환

가능한 시간복잡도

배열 내에서 슬라이딩 윈도우 → $O(nums.length) = O(n)$

최종 시간복잡도
$O(n)$ 이므로 충분히 동작할 수 있다.

알고리즘 선택

슬라이딩 윈도우

📌 코드 설계하기

필요 변수 정의
윈도우 오른쪽 옮기면서 탐색
2-1. 0이면 개수 증가
2-2. 윈도우 내 0이 2개 이상이면 0 1개 될 때까지 left 옮김
2-3. 현재 윈도우 길이 중 최댓값 갱신

📌 시도 회차 수정 사항

1회차

스택을 추가하고 nums에서 숫자 하나씩 확인하면서 1인지 0인지 등의 경우에 따라 |를 넣어서 1로만 이루어진 substring을 만들어보려고 했으나 고려해야 할 부분이 너무 많아서 구현하지 못했다.
슬라이딩 윈도우를 활용하는 방향으로 변경했다.

📌 정답 코드

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        # 윈도우 왼쪽 인덱스
        left = 0
        # 윈도우 내 0의 개수
        count_0 = 0
        # 최장 길이
        max_len = 0

        # 윈도우 오른쪽을 옮기면서 탐색
        for right in range(len(nums)):
            # 0이면 개수 증가
            if nums[right] == 0:
                count_0 += 1
            
            # 윈도우 내 0이 2개 이상이면 0이 하나 남을 때까지 left 움직임
            while count_0 > 1:
                # 0인 경우 개수 줄이기
                if nums[left] == 0:
                    count_0 -= 1
                
                # left 움직이기
                left += 1
            
            # 현재 윈도우 길이 중 최댓값 갱신
            max_len = max(max_len, right - left)
    
        return max_len

결과

👍 다른 풀이

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
    	# 배열에 1만 있을 경우
        if sum(nums) == len(nums):
            return(len(nums)-1)
            
        # 배열에 0만 있을 경우
        if sum(nums) == 0:
            return(0)
        
        # 0이 있는 인덱스를 모두 저장하는 리스트 정의
        locs = []
        
        # 0이 있는 인덱스 저장
        for i in range(len(nums)):
            if nums[i] == 0:
                locs.append(i)
        
        # 0이 하나면 그것만 제거한 길이 반환
        if len(locs) == 1:
            return(len(nums)-1)
        
        # 0이 여러 개 라면
        # 첫 번째 연속 구간 길이(첫번째 0과 두번째 0 사잉의 1로 이루어진 구간 길이) 계산
        size = locs[1] - 0 - 1
        
        # 최장 길이 초기화
        max_size = size
		
        # 여러 0 사이 구간 탐색
        # 두 번째 0부터 끝까지 하나씩 이동해 구간 계산
        if len(locs) > 2:
            for i in range(2, len(locs)):
            	# 인덱스 기준으로 거리 조정하며 0 제거
                size = locs[i] - locs[i-2] - 1 - 1
                max_size = max(size, max_size)
        
        # 마지막 0 이후로 남은 연속된 1 구간 길이 확인
        if locs[-1] < len(nums)-1:
            size = len(nums)-1 - locs[-2] - 1
            max_size = max(size, max_size)
        
        return(max_size)

Runtime : 2ms
이 풀이가 내가 원래 도전하려 했던 방향의 하나하나 경우를 따져서 구현하는 방식같다. 확실히 많이 복잡하고 비슷한 문제가 나왔을 때 직접 응용하기엔 어려울 것 같다.

✏️ 회고

지난 문제에 이어서 이 문제도 슬라이딩 윈도우를 활용하면 효율적으로 풀 수 있는 문제였다. 하지만 이 문제를 봤을 때 그 방식은 떠오르지 않았고 경우만 따지다가 시간이 다 가버렸다.
연속된 문자열 내용이 나오면 슬라이딩 윈도우, 투 포인터 방법이 매우 유용한 것 같다. 비슷한 유형을 보면 이 방식으로 도전해볼 수 있게 유형을 익혀두어야 겠다.