코딩테스트 파이썬/파이썬 프로그래머스 2단계
연속된 부분 수열의 합
세용용용용
2023. 6. 4. 20:57
나의 코드
def solution(sequence, k):
answer = []
for i in range(len(sequence)):
seq_sum = 0
for j in range(i,len(sequence)):
seq_sum+=sequence[j]
if seq_sum==k:
if len(answer)>0 and j-i < (answer[-1][1]-answer[-1][0]):
answer = []
answer.append([i,j])
else:
answer.append([i,j])
break
elif seq_sum > k:
break
#print(answer)
return answer[0]
solution([2, 2, 2, 2, 2], 6)
타임아웃 ㅋㅋㅋ 예상은 함 ㅋㅋ 이렇게 쉽게 풀릴리가 없지~~
def solution(sequence, k):
answer = [0,0]
seq_list = []
sequence = sequence[::-1]
for i in range(len(sequence)):
seq_num = 0
for j in range(i, len(sequence)):
seq_num+=sequence[j]
if seq_num == k:
if len(seq_list)>0:
if j-i > (seq_list[0][1] - seq_list[0][0]):
break
else:
seq_list.append([i,j])
else:
seq_list.append([i,j])
#print(sequence)
#print(seq_list)
answer[0] = (len(sequence)-1) - seq_list[-1][1]
answer[1] = (len(sequence)-1) - seq_list[-1][0]
#print(answer)
return answer
solution([1, 1, 1, 2, 3, 4, 5], 5)
역으로 풀어보았지만 타임아웃????
최종코드
def solution(sequence, k):
answer = []
seq_sum = 0
l=0
r=-1
while True:
if seq_sum < k:
r+=1
if r>=len(sequence):
break
seq_sum+=sequence[r]
elif seq_sum>=k:
seq_sum-=sequence[l]
if l>=len(sequence):
break
l+=1
if seq_sum==k:
answer.append([l,r])
answer.sort(key = lambda x: (x[1]-x[0], x[0]))
#print(answer)
return answer[0]
solution([1, 1, 1, 2, 3, 4, 5], 5)
후... 요즘 타임아웃에 너무 많이 걸린다 점점 갈수록 성격이 까다로워지는거 같음