문제
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
출력
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
예제
나의 풀이1
N, S = map(int, input().split())
nums = sorted(list(map(int, input().split())))
start, end = 0, 1
mn = N + 1
while start < end and end < N:
partial_sum = sum(nums[start:end+1])
length = end - start + 1
if partial_sum == S:
if length < mn:
mn = length
start += 1
end += 1
elif partial_sum > S:
if length < mn:
mn = length
start += 1
elif partial_sum < S:
end += 1
result = mn if mn <= N else 0
print(result)- 부분합이 타겟보다 큰지, 작은지, 같은지에 따라 두 포인터를 이동하면서 최소 길이의 수열을 찾는 방법으로 풀어봤다.
- 이 풀이는 시간 초과로 실패했다.
나의 풀이2
N, S = map(int, input().split())
nums = sorted(list(map(int, input().split())))
mn = N + 1
for start in range(N):
end = start + 1
while sum(nums[start:end+1]) < S and end < N:
end += 1
length = end - start + 1
if sum(nums[start:end+1]) >= S and length < mn:
mn = length
result = mn if mn <= N else 0
print(result)- for문을 실행하면서 `1`부터 `N-1`까지를 `start`로 가지는 수열의 부분합이 `S`이상인 최소 길이를 구한다.
- 이 풀이도 시간 초과로 실패했다.
다른 사람의 풀이
N, S = map(int, input().split())
nums = list(map(int, input().split()))
left, right = 0, 0
sum = 0
min_length = N + 1
while True:
if sum >= S:
min_length = min(min_length, right-left)
sum -= nums[left]
left += 1
elif right == N:
break
else:
sum += nums[right]
right += 1
result = 0 if min_length == N + 1 else min_length
print(result)- 두 포인터 모두 `0`부터 시작해서 현재 수열의 부분합이 타겟보다 크다면 `left`를 한 칸 이동하고, 부분합이 작다면 `right`을 한 칸 이동한다.
- 만약 오른쪽 포인터가 `N`에 도달한다면 while문을 종료한다.
- 부분합이 타켓보다 큰 경우의 if문 다음에 elif문에서 while문 종료를 설정한 이유는 오른쪽 포인터가 리스트의 끝에 도달했더라도 왼쪽 포인터를 이동하면서 새로운 수열의 부분합을 구할 수 있어야 하기 때문이다.
회고
- 비슷한 듯 다른 투포인터 알고리즘 문제들
- 기본적인 접근 방식은 맞히더라도 디테일의 차이로 문제를 계속 틀리고 있어서 아쉽다.
- 좀 더 세심하게, 시간복잡도를 고려하면서 문제를 풀어 보자!