글 읽기 - [파이썬] 시간초과 해결하는 방법..

ppirae 3년 전 0

투포인터 사용해봤는데 시간초과가 발생합니다 ㅠㅠ
어디가 문제점이고 해결하는 방법이 무엇인가요 ??

import sys
n, target = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
left, right = 0, 1
cnt = 0
while right < len(arr):
    sum = 0
    for i in range(left, right+1):
        sum += arr[i]
    if sum < target:
        right += 1
    elif sum > target:
        left += 1
    else:
        cnt += 1
        left += 1
        right += 1

print(cnt)

ehdrmsl2001 3년 전 1

합계를 매번 구하면 투 포인터를 쓰는 의미가 없습니다

right랑 left를 갱신할 때 합계도 같이 갱신 하시면 될 거 에요

djm03178 3년 전 1

투 포인터를 사용하는 것의 이점은 이전에 계산한 결과에서 포인터를 옮겨간 위치에 있는 것 하나만 연산을 추가하면 다시 답을 구할 수 있다는 점인데, 이 코드에서는 포인터를 옮길 때마다 확인중인 범위 전체를 재계산하기 때문에 효율적이지 않습니다. 시간 복잡도도 O(n^2)입니다.

ppirae 3년 전 0

감사합니다 투포인터 다시 공부해보겠습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[파이썬] 시간초과 해결하는 방법..

ppirae 3년 전 0

ehdrmsl2001 3년 전 1

djm03178 3년 전 1

ppirae 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말