소마 구현쪽에 투포인터 나왔다는 소리가 있어 어제 하루종일 투포인터 공부하느라 게시글을 못올렸습니다 ㅜㅜ...
하지만 큰 수확이 있었으니...바로 골드4 투포인터 문제를 자력솔 했습니다!

1806번 - 부분합

수열이 주어지면 S보다 크거나 같은 부분수열의 합 중에서 가장 크기가 작은 부분수열을 구하면 되는 문제입니다.

---

분석

일단 위 문제에 나온 수열을 그대로 가져왔습니다. 여기서 투포인터 개념을 적용할겁니다.

lst.popleft()를 통해 값의 합이 15가 되기 전까지 원소를 계속 긁어옵시다.

그런데 긁어오다 보니 값의 합이 15를 넘은 24가 되었습니다!
이러면 조건에 만족하는 부분수열이니 해당 부분수열의 크기를 따로 기록하고
최종적인 목적은 15가 넘는 제일 작은 크기의 부분수열이니 quene를 pop해서 최대한 크기를 줄여봅시다.

5를 popleft해도 19가 되므로 이 수열 크기(4)또한 따로 기록해두고 더 빼봅시다.

1을 popleft해도, 3을 popleft해도 15보다 크거나 같으므로 부분수열의 크기를 따로 기록해두고 더 뺴봅시다.

드디어 10만 남게되어 조건을 만족하지 못합니다. 이제 윗부분으로 다시 돌아가서 합산 15이상이 될때까지 lst에서 원소를 다시 긁어옵시다.

투포인터란 이처럼 시작점과 끝점을 잡고 조건을 만족하지 못하면 끝점을 늘리고 조건을 만족하면 시작점을 빼는 형식의, 이중 for문으로 O(N^2)에 처리되는 작업을 2개의 포인터의 움직임으로 O(N)에 해결하는 알고리즘입니다.

출력값을 통해 과정을 살펴보면 위와 같은 느낌입니다.

---

코딩

위 과정을 코딩해봅시다.

from collections import deque
import sys

input = sys.stdin.readline

해당 문제는 시간제한이 0.5초로 매우 급박하므로 sysinput을 사용해줍니다.

N,S = map(int,input().split())
lst = deque(list(map(int,input().split())))

배열의 크기, 합산 조건, lst등을 받아주고

quene = deque([lst[0]])

투포인터를 사용할 que를 하나 만들어줍니다.

    cum_sum = lst[0]
    lst.popleft()
    min = 100000001

한가지 주의할 점이 있습니다. 부분배열의 합산값을 구할때 sum(부분배열)을 하게되면 sum 함수를 100000번 가까이 사용해야 하므로 시간제한에 거릴 확률이 굉ㅡ장히 높습니다. 따라서 누적합을 cum_sum을 통해 따로 기재해주겠습니다.

    while True:
        try:
            if cum_sum < S:
                tmp1 = lst.popleft()
                cum_sum += tmp1
                quene.append(tmp1)

만약 부분수열의 합이 위 예시에서 봤던 것처럼 15보다 작아 조건을 만족하지 못한다면 lst에서 원소를 긁어와 quene에 추가해줍시다.

            else:
                if len(quene) < min:
                    min = len(quene) 
                tmp2 = quene.popleft()
                cum_sum -= tmp2

만약 조건을 만족한다면 조건을 만족하는 quene의 길이 중에서 제일 작인 길이를 quene에 넣어주도록 합니다.

        except:
            break

quene을 다써서 예외가 날 경우엔 break으로 처리해주고

print(min)

마지막으로 min을 출력하면 끝날 것 같지만

골드의 벽은 그렇게 호락호락하지 않습니다...

---

반례

로직이 올바른데 틀리게 나온다면 항상 반례를 생각해봐야 합니다.

1. 테스트케이스가 10/10/11113211111 일때

한 가지 숫자가 조건 S를 만족시킬만큼 S보다 크게 나와버린다면 답은 무조건 1이 됩니다.

2. min이 제 역할을 못해서 그대로 나와버릴 경우

만약에 뭘 해도 합산 S가 만족되지 않는다면

            else:
                if len(quene) < min:
                    min = len(quene) 
                tmp2 = quene.popleft()
                cum_sum -= tmp2

구문 자체가 실행되지 않아 최솟값을 구하려고 둔 min값이 초기값 100000001로 그대로 유지되게 됩니다.
이 두 경우를 고쳐봅시다.

---

for values in lst:
    if values >= S:
        boolean = True
if boolean == True:
    print(1)
else:

투포인터 코드를 실행시키기 전에 원소들을 다 검사해서 S보다 크거나 같은 원소가 있으면 1을 출력해줍시다.

    if min >= 100000001:
        print(0)
    else:
        print(min)

min값이 초기화값 그대로 나와버린다면 S조건을 아예 만족시키지 못하는 경우이므로 0을 출력합시다.

---

전체코드

from collections import deque
import sys

input = sys.stdin.readline
N,S = map(int,input().split())
lst = deque(list(map(int,input().split())))
quene = deque([lst[0]])
sum_list = sum(lst)
boolean = False
for values in lst:
    if values >= S:
        boolean = True
if boolean == True:
    print(1)
else:
    cum_sum = lst[0]
    lst.popleft()
    min = 100000001

    while True:
        try:
            if cum_sum < S:
                tmp1 = lst.popleft()
                cum_sum += tmp1
                quene.append(tmp1)
            else:
                if len(quene) < min:
                    min = len(quene) 
                tmp2 = quene.popleft()
                cum_sum -= tmp2
        except:
            break

    if min >= 100000001:
        print(0)
    else:
        print(min)

---

---