2003번 수들의 합2

문제 출처 : https://www.acmicpc.net/problem/2003

사고과정

선형적인 list에서 연속적인 값들을 요소로 하여 주어진 값과 비교. O(n)으로 풀 수 있을 듯!

주어진 값과 비교할 요소값들을 모은 list를 s라고 하자.
s+new가 M보다 작다면 다음 요소를 조회하여 조사한다.
s+new가 M보다 크다면 어차피 s의 첫번째 요소를 삭제해야 한다. new를 조회한 시점에서 이미 s<M은 전제되어 있기 때문이다. WHILE문을 이용해 s+new가 M보다 작아질때까지 요소를 삭제한다. ( 이 때 놓친 부분이 있다면 new가 M보다 클 수도 있다. 이럴 경우에는 절대로 더해서 M을 만들어 낼 수 없기 때문에 CLEAR 시켜주고 다음 값을 조회 )
s+new가 M과 값다면 result에 1을 더해준다.

import sys

N,M = list(map(int,sys.stdin.readline().rstrip("\n").split()))
num = list(map(int,sys.stdin.readline().rstrip("\n").split()))
s = [0]
result=0

for i in range(N) :
    if num[i]>M :
        s=[0]
        continue
    while sum(s)+num[i]>M :
        s.pop(0) #만약 모든 요소가 없다면? num[i]가 M보다 커
    s.append(num[i])
    if sum(s)==M :
        result+=1

print(result)

다른 사람들의 풀이보다 10배에 준하는 시간이 걸린다. 더 효율적으로 작성가능
나름 상당히 O(n)으로 줄이고, s라는 배열을 이용할 게 아니라 real 투포인터로 left, right도 사용해봤는데 더 오래 걸리네... 다른 사람들이 어떻게 작성했는지 참고하고 배우자.
원리는 유사한 것 같은데... 나처럼 pop을 쓴 게 아니라 투 포인터를 직접적으로 이용해서 just 숫자로 계산하였다. 나는 사실 코드를 뜯어보면 투 포인터를 직접적으로 이용하기 보단 stack과 투포인터의 원리를 이용하여 추상적으로 이를 작성했다.

import sys

N,M = list(map(int,sys.stdin.readline().rstrip("\n").split()))
num = list(map(int,sys.stdin.readline().rstrip("\n").split()))
left,s = 0,0
result=0

for i in range(N) :
    if num[i]>M :
        left =i+1
        continue
    s+=num[i]
    while s>M :
        s-=num[left]
        left+=1
    if s==M :
        result+=1

print(result)

left,right 변수를 이용하여 투 포인터를 이용할수도 있지만 처음 착안한 방식에서 다른 사람의 아이디어와 이론들을 수정하여 내 것으로 만드는 게 더 중요하다 생각해서 내 방식을 고수하고 변형했다. while문을 이용하기보다는 처음 그대로 for문으로 하나씩 전진하면서 이전부분을 계산한다. for문의 i가 투포인터의 right 역할을 하는 것이다.

비교 결과

압도적으로 빠르다~!!

다들 stack을 이용하기 보다는 정수형을 이용해서 직접적으로 계산했다. 이게 훨씬 빠르긴 하지. list가 상당히 효용성있고 편한 건 맞지만 너무 의존할려고는 하지말자.