반응형
https://school.programmers.co.kr/learn/courses/30/lessons/178870
def solution(sequence, k):
prefix_sum = [0]
sum_value = 0
s = 0
e = s+1
result = [0, len(sequence)]
for i in range(len(sequence)):
sum_value += sequence[i]
prefix_sum.append(sum_value)
while s < e and e < len(prefix_sum):
if prefix_sum[e] - prefix_sum[s] == k:
if (e-1) - s < (result[1] - result[0]):
result = [s, e-1]
e += 1
elif prefix_sum[e] - prefix_sum[s] < k:
e += 1
else:
s += 1
return result
이 문제는 이전에 풀었던 문제와 유사합니다.
완전 탐색으로 푸는 것이 아니라 누적합을 구하여 문제를 해결했습니다.
먼저 prefix_sum 리스트에 sequence 리스트의 원소들을 누적합하여 구합니다.
prefix_sum의 첫번째 원소는 0입니다.
prefix_sum[1] : sum(sequence[:1])
prefix_sum[2] : sum(sequence[:2])
prefix_sum[3] : sum(sequence[:3]) 입니다.
while문으로 k와 동일한 부분수열의 합을 찾게됩니다.
이때 prefix_sum의 인덱스를 s, e 변수로 찾게 됩니다.
- s는 0부터 시작하고 e는 s+1부터 시작합니다.
while문의 종료조건은 s 가 e보다 커지거나 e가 prefix_sum의 범위를 벗어나면 종료합니다.
먼저 부분수열의 합이 k와 동일하다면 부분수열의 길이가 기존의 길이(result)보다 짧은지 확인하고 짧다면 result를 갱신합니다.
- 0부터 시작하기 때문에 항상 result에 저장되어있는 인덱스가 앞쪽에 나오는 수열입니다.
그리고 e 인덱스를 증가시킵니다.
만약 k보다 작다면 e 인덱스를 증가시키고 k보다 크다면 s 를 증가시킵니다.
여기서 2중 반복문으로 모든 인덱스를 탐색하면 시간초과가 나오기 때문에 s,e 인덱스를 만들어 투포인터로 진행하였습니다.
반복문이 종료되었다면 result를 반환합니다.
반응형
'코딩테스트' 카테고리의 다른 글
[코딩테스트] 백준 후위표기식(2)(1935) 파이썬(Python) (0) | 2023.04.17 |
---|---|
[코딩테스트] 백준 숨바꼭질3(13549) 파이썬(Python) (0) | 2023.04.13 |
[코딩테스트] 백준 숨바꼭질(1697) 파이썬(Python) (0) | 2023.04.11 |
[코딩테스트] 백준 두 수의 합(3273) 파이썬(Python) (0) | 2023.04.10 |
[코딩테스트] 프로그래머스 추억 점수 파이썬(Python) (0) | 2023.04.07 |