출처: https://www.acmicpc.net/problem/15565
문제부터 분석해봅시다
일단 조건부터 따지겠습니다. 시간 제한은 1초이고 N은 1,000,000 까지 제한이 되어있습니다.
위의 조건을 따져보면, 1,000,000 * 100 회까지 연산이 제한된 셈인데, 결론은 복잡도도 꽤나 빡세게 적용을 할 수 있는 문제라는 것입니다.
그런데 이 문제는 생각보다 간단하게 해결이 가능합니다. 다음 문단에서 왜 그런지 알려드리겠습니다.
이 문제는 어떻게 해결해야할까요?
일단 출력 조건을 분석해보겠습니다.
K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 출력하여라
위의 출력을 내기 위해서는 아래의 원칙을 지켜주면 됩니다.
- subsequence의 처음과 끝은 무조건 라이언이 있어야합니다.
이 원칙을 생각해보면, 저희는 아래의 방법으로 문제를 풀 수 있습니다.
- 라이언이 있는 인덱스만 따로 리스트로 쭉 뽑아내서 거기서 계산을 하자.
위의 방법대로 문제를 풀게되면 저희는 선형복잡도에 가까운 형태로 문제를 해결할 수 있을겁니다. 코드를 봅시다!
코드를 봅시다
import sys
# 15565 귀여운 라이언
input = sys.stdin.readline
N, K = map(int, input().split())
doll_list = list(map(int, input().split()))
lion_list = []
for i, doll in enumerate(doll_list):
if doll == 1:
lion_list.append(i)
if len(lion_list) < K:
print(-1)
else:
start, end = 0, len(lion_list) - K
minv = lion_list[K - 1] - lion_list[0] + 1
while start <= end:
size = lion_list[start + K - 1] - lion_list[start] + 1
if size < minv:
minv = size
start += 1
print(minv)여기서는 while의 범위만 잘 잡아주면, 나머지는 진짜로 쉽습니다.
🌈 예시 입력
10 3
1 2 2 2 1 2 1 2 2 1🌈 lion_list
0 4 6 9위의 예시를 따져보면, 저희는 라이언이 3개가 있는 가장 크기가 작은 subset의 크기를 구해야합니다. 그러면 lion_list에서는 1번 인덱스부터 4번 인덱스까지 구간을 잡는게 마지막 슬라이딩 윈도우가 될텐데, 그러면 start는 1 까지만 제한을 해줘야할겁니다.
이를 일반화 시키게되면, start는 정확히 len(lion_list) - K 까지 제한을 걸고 while을 돌리면 된다는 뜻입니다.
위의 조건을 가지고 길이가 K인 슬라이딩 윈도우에서 subset 크기를 매번 계산해서 minv를 갱신하면 문제는 해결이됩니다.
