•
문제 설명 : 0과 1만 존재하는 배열 중, 0을 하나만 제외하였을 때 가장 긴 1의 연속된 길이가 몇인지 반환
•
풀이 방법
◦
Sliding Window 문제였다.
◦
다만, 다른 문제처럼 각 탐색범위를 1씩 이동하면 시간 초과 오류가 발생하기 때문에 매 탐색범위의 조정이 가장 중요했다.
▪
그래서, 0을 처음 발견한 위치를 다음 탐색 시작 위치로 설정하였다.
•
시간복잡도 :
•
성공 코드
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
cursor, start_cursor = 0, 0
max_count = 0
# 탐색을 끝까지 한다면 바로 종료
while start_cursor < len(nums) and cursor < len(nums):
# 각 탐색 시작 위치를 변경
cursor = start_cursor
# 탐색 시 1의 갯수와 0을 건너뛰었는지 여부
count = 0
is_delete_zero = False
# 각 탐색 범위 중 연속된 1의 길이 확인
while cursor < len(nums):
# 0을 발견 시
if nums[cursor] == 0:
# 아직 0을 건너뛴적이 없는 경우
# 다음 탐색 시작 위치를 첫 0이 발생한 위치로 설정
if not is_delete_zero:
is_delete_zero = True
start_cursor = cursor
# 이미 0을 건너뛴적이 있는 경우 탐색 중단
else:
break
# 1일 경우에는 숫자 증가
else:
count += 1
cursor += 1
# 매 탐색마다 카운트 갱신
max_count = max(max_count, count)
# 탐색에서 처음 0을 발견한 위치 바로 다음 위치에서 다음 시작
start_cursor += 1
# 0이 아예 존재하지 않는 경우 1을 빼고 반환
return max_count - 1 if max_count == len(nums) else max_count
Python
복사