문제 소개
배열 nums와 정수 k가 주어졌다고 가정해 봅시다. 이때 "nice 부분 배열"의 개수를 구하는 것이 목표입니다. 부분 배열(subarray) 안에 정확히 k개의 홀수가 포함되어 있으면, 그 부분 배열을 nice 부분 배열이라고 정의합니다.
예를 들어, 입력이 nums = [1,1,2,1,1], k = 3이라면 출력은 2가 됩니다. 조건을 만족하는 부분 배열이 [1,1,2,1]과 [1,2,1,1] 두 개뿐이기 때문입니다.
접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
홀수의 위치(인덱스)를 저장할 새 리스트
odd_i를 생성합니다.i를 0부터 nums의 길이 - 1까지 반복하면서,
nums[i] % 2 == 1즉 nums[i]가 홀수이면 해당 인덱스 i를odd_i의 끝에 추가합니다.start = 0,end = k - 1,i = 0,count = 0으로 초기화합니다.end가odd_i의 길이보다 작은 동안 다음을 반복합니다.만약
end == len(odd_i) - 1이면 마지막 홀수까지가 범위이므로j = len(nums) - 1로 설정합니다.그렇지 않으면
j = odd_i[end + 1] - 1로 설정하여 다음 홀수 바로 앞까지만 확장 가능하게 합니다.count += (odd_i[start] - i + 1) * (j - odd_i[end] + 1)을 계산해 더합니다. 왼쪽으로 확장 가능한 경우의 수와 오른쪽으로 확장 가능한 경우의 수를 곱한 값입니다.i = odd_i[start] + 1,start += 1,end += 1로 갱신하여 다음 창(window)으로 이동합니다.
반복이 끝나면 최종
count를 반환합니다.
핵심 아이디어는 먼저 모든 홀수의 인덱스를 추출한 뒤, 연속된 k개의 홀수를 포함하는 각 구간에 대해 양쪽으로 늘릴 수 있는 부분 배열의 개수를 곱셈으로 한 번에 계산하는 것입니다. 이 방식은 배열을 여러 번 순회하지 않고도 효율적으로 답을 구할 수 있습니다.
예제 코드
아래 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(nums, k):
odd_i = []
for i in range(len(nums)):
if nums[i] % 2 == 1:
odd_i.append(i)
start = 0
end = k - 1
i = 0
count = 0
while end < len(odd_i):
if end == len(odd_i) - 1:
j = len(nums) - 1
else:
j = odd_i[end + 1] - 1
count = count + (odd_i[start] - i + 1) * (j - odd_i[end] + 1)
i = odd_i[start] + 1
start = start + 1
end = end + 1
return count
nums = [1,1,2,1,1]
k = 3
print(solve(nums, k))
입력
[1,1,2,1,1] 3
출력
2
마무리
이 알고리즘은 홀수 인덱스만 별도로 관리하기 때문에 시간 복잡도는 O(n)이며, 배열의 길이가 커져도 효율적으로 동작합니다. 슬라이딩 윈도우와 조합 계산을 결합한 대표적인 기법이므로 유사한 부분 배열 문제에도 응용할 수 있습니다.