탐색&시뮬레이션 문제 #5. 수들의 합

*이 풀이는 인프런: 파이썬 알고리즘 문제풀이 강좌에 기반하였습니다.

 

 

 

내 풀이 ( 80점, 마지막 문제 시간 초과) : O( N^2 )

 

1. i번째부터 수를 순차적으로 더해 나가다가 그 합이 m이 되는 경우, cnt값을 증가시키고 break를 통해 시작위치(i)를 다음 칸으로 옮긴다.

2. 합이 m보다 큰 경우, 더이상 더해봤자 의미없으므로 break를 해서 시작위치(i)를 다음 칸으로 옮긴다.

 

import sys
#sys.stdin=open("input.txt","rt")

n,m=map(int, input().split())
arr=list(map(int,input().split()))

cnt=0
sum=0

for i in range(n):
    sum=0
    for j in range(i,n):
         sum+=arr[j]
         if sum==m:
            cnt+=1
            break
         elif sum>m:
            break
print(cnt)

 

 

 

강사님 풀이 : O( N )

 

import sys
#sys.stdin=open("input.txt","rt")

n,m=map(int, input().split())
a=list(map(int,input().split()))

lt=0
rt=1
tot=a[0]
cnt=0

while True:
    if tot<m:
        if rt<n:
            tot+=a[rt]
            rt+=1
        else: #rt=n
            break
    elif tot==m:
        cnt+=1
        tot-=a[lt] #'-'연산에 의해서 결국 마지막에는 모두 tot<m의 경우로 귀결된다. 
        lt+=1
    else: #tot>m
        tot-=a[lt]
        lt+=1

print(cnt)

 

 

 

배운 점

 

1. 1차원 배열을 탐색하는 경우, 포인터(변수를 포인터처럼 사용)를 이용해서 배열에서 원하는 값을 가리키게 하자.

 

2. 1차원 배열의 순차 탐색인 경우, 포인터를 사용해서 충분히 O(N) 으로 해결할 수 있다. 내 풀이는 이중 for문으로 O(N^2)의 시간복잡도를 가지게 되어, 마지막 문제에서 시간 초과가 났다. O(N^2)은 파이썬에서 시간 초과가 나는 경우가 많기 때문에, 1차원 배열에서 이중 for문은 왠만해서 사용하지 않도록 한다.