입출력 예시
sequence k result
[1, 2, 3, 4, 5] 7 [2, 3]
[1, 1, 1, 2, 3, 4, 5] 5 [6, 6]
[2, 2, 2, 2, 2] 6 [0, 2]
문제 전체를 다 가져오기 귀찮아서 예시만 가져왔다.
(친구가 코테는 문제 읽는 데에도 시간이 엄청 걸린다고 한다. 동감한다)
오름차순으로 되어 있는 시퀀스에서 합 k를 만족시키는 부분합의 인덱스를 구하면 되는 문제.
즉 [2, 3]은 인덱스가 2인 3 + 인덱스가 3인 4 = k값 7 을 만족시킨 것이다.
또 다른 케이스로는, k값을 만족시키는 부분합이 여러개 (1+1+1+2, 2+3, 5)가 있을 때 가장 길이가 짧은 부분합을 구하면 되고 마지막 케이스는 k값을 만족시키는 길이가 같은 부분합이 여러개 있을 경우 가장 최초의 것을 가져오면 된다.
나의 풀이
테스트케이스가 34개 정도였고, 내 풀이로는 시간복잡도가 꽤나 크게 나와서 정확도 44.1%에 그쳤다.
def solution(sequence, k):
N = len(sequence)
answer = [0,N-1]
for i in range(N):
seq_sum = sequence[i]
right_i = i
while seq_sum < k:
right_i +=1
if right_i < N:
if k == seq_sum + sequence[right_i]:
seq_sum += sequence[right_i]
break
else:
seq_sum += sequence[right_i]
else:
break
if seq_sum == k:
if right_i - i < answer[1] - answer[0]:
answer = [i, right_i]
elif seq_sum > k:
pass
return answer제일 첫번째 for문에서 전체를 돈다 (n)
그리고 그 안의 while문에서도 seq_sum < k라는 조건을 만족시키지 않을 때까지 작업을 수행한다.
추측컨대 테스트 케이스 중 이 while문의 복잡도를 n으로 만드는 케이스가 있었을 것이다. 그래서 시간복잡도 O(n^2)의 풀이가 되었다. 그래서 정확도 44.1에 그쳤다. 답은 잘 나온다 ㅋㅋ
그럼 어떻게 시간 내에 맞추어 푸느냐?
투포인터 알고리즘을 사용하면 된단다.
모범 답안
def solution(sequence, k):
N = len(sequence)
answer = [0,N-1] # answer의 기본값
left, right = 0, 0
seq_sum = sequence[left]
while right < N:
if seq_sum == k:
if right - left < answer[1] - answer[0]: # answer 사이의 간격보다 좁을 경우, 즉 부분합 길이가 더 짧을 경우에만
answer = [left, right]
seq_sum -= sequence[left] # 기존의 seq_sum에서 left의 값을 빼준다
left += 1 # left가 0인 경우에서 k를 만족시키는 부분합을 발견했으므로 left 포인터를 옮김
elif seq_sum < k:
right += 1 # seq_sum이 k보다 작을 경우 right 포인터를 옮김
if right < N: # IndexError를 예방
seq_sum += sequence[right]
else: # seq_sum이 k보다 클 경우
seq_sum -= sequence[left] # left의 값을 빼준다
left += 1 # left가 0인 경우에서는 k를 만족시키는 부분합이 없으므로 left 포인터를 옮김
return answer챗gpt의 도움을 받았다. 다른 사람의 풀이를 보고는 도저히 이해를 할 수 없었기 때문이다.. 내 풀이를 프롬프트로 사용하니 시간복잡도가 문제였다고 지적하고 반복문을 한 번만 써서 투포인터 알고리즘을 사용하라고 했다. 정말 모범답안이 아닐수가 없다. 다른 사람들 답안보다도 훨씬 좋다고 생각한다. (신통방통하다)
무엇보다도 시간복잡도를 해결하려고 해괴한 코드를 짜는 것을 너무 많이 봤다.
클린 코딩합시다... 람다 쓸 필요 없는데 왜 쓰는거야
당분간은 코테 연습 좀 하면서 머리에 기름칠을 좀 해야겠다. 끝
