백준 2003 파이썬

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

사고 과정

1. M 이랑 매칭될 때까지 차례로 더하거나
2. M 보다 커지면 break
3. 어떻게 M 을 맞추느냐는 관심없다.  연속된 숫자의 몇가지 경우가 M 을 맞추는지가 중요.

 

정답 코드

from sys import stdin


N, M = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))
count = 0
left, right = 0, 1

if arr[0] == M:
    count += 1
while right < len(arr):
    total = sum(arr[left: right + 1])
    if total < M:
        right += 1
    elif total > M:
        left += 1
    else:
        count += 1
        left += 1
        right += 1


print(count)

 

처음 풀이 (오답)

이중 for 문으로 접근했다. 풀면서도 당연히 시간초과가 날 것이라 예상했다. 리스트 슬라이싱으로 인해 사실상 시간복잡도 O(N^3)... 

반복문을 한번만 돌리되 두번 돌린 것 같은 효과를 내는 것, 그것이 이번 문제(two pointer 라고 하더라)를 푸는 핵심이다.

두번 돌린 것 같은 효과를 내려면 어떻게 해야할까?

두번째 for 문을 살펴보면, j 인덱스의 값을 증가시키면서 반복문을 진행한다. j 인덱스는 i 이후의 인덱스를 나타낸다.

그럼 j 인덱스를 자동으로 증가시킬수만 있다면, 두번째 for 문은 사용하지 않아도 된다는 결론에 도달했다.

from sys import stdin


N, M = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))
count = 0

for i in range(N):
    for j in range(i + 1, N + 1):
        temp = sum(arr[i:j])
        if temp == M:
            count += 1
            break

        elif temp > M:
            break
print(count)

 

 

더 빠른 풀이

내가 푼 정답코드는 리스트 슬라이싱을 사용하기 때문에 시간복잡도가 O(N^2) 가 되어 속도가 느리다. 

아래 코드는 리스트 슬라이싱을 사용하지 않고 연속된 원소의 합을 구하여, 풀이 속도를 줄인 케이스다.

 

while True 문의 탈출 조건으로는 right 변수가 배열의 크기보다 커지는 순간으로 정했다. 그 전까지는 계속 반복문을 돌면서 두 변수(left, right)와 합계(total)을 조절한다. 합계를 구할 때 슬라이싱을 사용하지 않고, 곧바로 인덱스로 접근하므로 시간복잡도에서 우위를 갖는다( = 더  빠르다)

N, M = map(int, input().split())
A = [ int(x) for x in input().split() ]

left = 0
right = 0
total = 0
ans = 0

while True:
    if total >= M:
        total -= A[left]
        left += 1
    elif right == N:
        break
    else:
        total += A[right]
        right += 1
    if total == M:
        ans += 1

        
print(ans)

 

 

배운 것

- two pointer 라는 접근법

- slicing은 시간복잡도 O(N)