[백준 15565] 귀여운 라이언

문제

꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하여라.

입력

첫 줄에 N과 K가 주어진다. (1 ≤ K ≤ N ≤ 106)

둘째 줄에 N개의 인형의 정보가 주어진다. (1 또는 2)

출력

K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 출력한다. 그런 집합이 없다면 -1을 출력한다.

---

풀이

처음에 문제를 잘못 해석하여 이상한 코드를 하나 짜고 다시 방법을 생각했다

 

정리해보면 라이언 인형이 K개 이상 들어있는 연속부분수열을 전부 탐색하고 가장 짧은 길이를 출력해야한다

N과 K의 범위를 얼핏봐도 완전탐색은 말이 안되고 처음부터 끝까지 한번만 훑으며 탐색해야 할 것 같다

 

연속 부분수열의 양쪽 끝을 가리키는 포인터변수를 두개 사용해도 좋지만 큐를 사용하여 탐색해보기로 했다

K = 3 일때,

 

A = [1 2 2 2 1 2 1] 2 2 1

pointer = [0,4,6]

 

A = 1 2 2 2 [1 2 1 2 2 1]

pointer = [4,6,9]

 

위와 같은 방법으로 1의 위치를 담는 poiter를 사용한다

1. A[idx] == 1 이면 idx를 pointer에 뒤쪽에 push 해준다

2. pointer 원소의 개수가 K와 같아지면 poiter[-1] - pointer[0] + 1 로 연속부분수열의 길이를 검사한다

3. 검사 후에는 pointer의 가장 앞 원소를 빼주고 다시 1번으로 돌아간다

 

for idx in range(N):
    if dolls[idx] == 1:
        rion_pointer.append(idx)
        rion_cnt += 1
    if rion_cnt == K:
        first = rion_pointer.pop(0)
        if res > idx-first+1:
            res = idx-first+1
        rion_cnt -= 1

 

 

처음에는 리스트를 큐로 사용했더니 시간초과가 났다

시간복잡도는 O(N)으로 100만회 연산에서 시간초과가 난다면 pop(0)이 문제

pop()은 상수시간이 걸리지만 pop(0)은 전방의 원소를 제거하고 리스트를 한칸씩 당기는 작업으로 O(n)이 걸린다

 

rion_pointer = Queque()

for idx in range(N):
    if dolls[idx] == 1:
        rion_pointer.put(idx)
        rion_cnt += 1
    if rion_cnt == K:
        first = rion_pointer.get()
        if res > idx-first+1:
            res = idx-first+1
        rion_cnt -= 1

 

queue를 사용하면 통과한다

 

rion_pointer = deque()

for idx in range(N):
    if dolls[idx] == 1:
        rion_pointer.append(idx)
        rion_cnt += 1
    if rion_cnt == K:
        first = rion_pointer.popleft()
        if res > idx-first+1:
            res = idx-first+1
        rion_cnt -= 1

 

 

하지만 deque가 훨씬 빠르다

파이썬에서 queue는 멀티쓰레드 환경의 안정성을 보장하기 위해 설계되었기에 deque가 더 빠르다고 한다