연속된 부분 수열의 합

📖 연습문제 > 연속된 부분 수열의 합

📖What I thought

<1차 시도> sum([st:en+1])를 구하는 문제니까 투포인터로 끝까지 돌자

Note

k보다 작으면 en++ 크면 st++ 같으면 list append & en++ st++

list에는 합이 k인 모든 부분수열이 들어있음 (조건) 여러 개면 길이가 짧아야 해 → lamda식으로 길이순 len(x)정렬 엥 만족하는 부분수열 리턴이 아니라 그때의 시작/끝 인덱스 리턴이였음… 그럼[i1, i2]로 list append해서 i2-i1이 가장 작은 순 x[1]-x[0]으로 람다식 정렬 그러고 가장 앞 요소 리턴하자 !!!

시간 초과…

<2차 시도> ⭐️비내림차순 → 뒤에서부터 부분합 찾기 ∵비내림차순이라서 뒤로 갈수록 원소 개수 줄어듦

Note

k보다 작으면 st— 크면 en— 같으면 st— en—

length가 같으면 계속 앞으로 가서 만족하는 부분수열 더 찾아(조건)인덱스 앞 length보다 en-st가 더 크면 순회 중단 ⭐️탐색횟수를 최소화가 키포인트⭐️

또 시간초과…

<3차 시도> 반복문 돌 때마다 sum함수를 계속 사용해서 시간초과였단 걸 깨달음 이거 때문에 무조건 O(n^2)ㅋㅋ 걍 처음에 합 구해주고 포인터 움직이는대로 요소 추가하고 제거하기로 함 그러면 그냥 앞에서부터 클래식하게 투포인터 가면 됨

📖풀이

📎투포인터

def solution(sequence, k):
    answer = []
 
    n = len(sequence)
    length = n+1
    st = en = 0
    sub_sum = sum(sequence[st:en+1])
    
    while st<n and en<n:
        # 작으면 요소 추가
        if sub_sum < k:
            en += 1
            
            # 수열 끝을 넘은 경우
            if en == n:
                break
            
            sub_sum += sequence[en]
        # 크면 요소 제거
        elif sub_sum > k:
            sub_sum -= sequence[st]
            
            st += 1
            
        # 같으면 킵
        else:
            # 더 짧은 부분 수열 발견
            if length > en - st + 1:
                answer = [st, en]
                length = en - st + 1
                
            sub_sum -= sequence[st]
            st += 1
                
    return answer

📖What I learned

1. 조건이 조금 더 붙은 클래식한 투포인터 문제 → 투포인터 연습할 때 참고하기!
2. 시간복잡도를 잘 계산하자!
3. 반복문 조건이 애매했는데 처음엔 그냥 for문으로 st한 번 en이 한 번씩 각각 끝까지 돌면 2n이니까 for문으로했는데 이러니까 계속 예외처리도 해줘야하기도 하고 while 문으로 둘 다 n보다 작을 때로 하면 더 직관적인 것 같아서 수정! 이렇게 while문으로 하면 st의 경우에는 반복문 내에서는 범위 확인하지 않아도 됨. 왜냐면 n을 넘어도 초과된 인덱스의 요소는 사용하지 않는데다가(값을 제거함) 다음 루프에서 자동으로 조건 체크됨 en은 확인 필요함 오른쪽 인덱스 얘는 값이 추가되는 것

📖관련 지식