•
문제 설명 : 0과 1이 반복되는 배열 중, 0을 1로 바꾸었을 때 가장 긴 연속된 1의 길이를 반환
•
풀이 방법
◦
아이디어가 떠오르지 않아서, Solution의 내용을 확인했다.
◦
우선 기초적인 아이디어는 K 값을 증감하며, 탐색 범위를 조정하는 아이디어이다.
▪
기본적으로 우측 커서만 하나씩 증가한다.
▪
만약 0의 갯수가 K의 갯수보다 더 많다면, 왼쪽 커서를 이동시킨다.
•
이때 범위에서 제외되는 왼쪽커서가 0이었다면, 0을 하나 더 뒤집을 수 있기 때문에 K를 증가시킨다.
▪
왼쪽 커서를 최대한 안움직이려는 이유는, 최대한 긴 값을 반환하는 문제의 조건 때문이다.
•
시간복잡도 :
•
성공 코드
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
left = 0
for right in range(len(nums)):
# 변경 가능한 0이 존재하는 경우, K 감소
if nums[right] == 0:
k -= 1
# 변경 가능한 0의 갯수가 더 많아진 경우
if k < 0:
# 만약 가장 왼쪽에 있는 0을 변경할 수 있다면
if nums[left] == 0:
k += 1
# 0을 채울 수 있는 상황이 될 때까지 left 커서 이동
left += 1
return right - left + 1
Python
복사