[Programmers] 연속된 부분 수열의 합 (Python)

📖문제

코딩테스트 연습 - 연속된 부분 수열의 합 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

✨핵심 내용 

합이 k인 부분 수열의 시작 인덱스와 마지막 인덱스를 반환
- 합이 k 인 부분 수열이 여러 개 일 경우 길이가 짧은 수열 반환
- 길이가 짧은 수열이 여러 개인 경우 시작 인덱스가 작은 수열 반환

입출력 예시

 

🤔해결 아이디어 

유형: 투포인터

1. start 포인터를 기준으로 end 포인터를 이동시킨다 (for 문)

2. 만약 부분 수열의 합이 k라면 (시작 인덱스, 마지막 인덱스, 배열의 길이)의 값을 ans에 추가한다 

3. 만약 부분 수열이 합이 k 보다 작다면, 현재 end 위치의 값을 더해주고 end 값을 이동시킨다

4. 만약 부분 수열의 합이 k 보다 크다면, while 조건을 만족하지 못하고 다음 start 분기로 이동한다 

5. 길이를 기준으로 정렬한 뒤 결과를 반환한다

 

🟡주의할 점

- while 조건, 인덱스 범위를 주의해야 한다 

---

✅정답 코드 (Python)

🟡 sol1) start를 for 문을 사용하여 이동

def solution(sequence, k):
    n = len(sequence)
    end = 0
    total = 0
    ans = []
    
    # start를 기준으로 인덱스 이동 
    for start in range(n):
        while total < k and end < n:
            total += sequence[end] # 현재 까지 부분 수열의 합 계산
            end += 1 # 인덱스 이동 
            
        # 조건 만족시 
        if total == k:
            ans.append((start, end -1, end - 1 - start)) # start, end, 길이
        
        # total > k or end >= n 이면 
        total -= sequence[start] # start 이동 전 값 빼주기 
    
    # 길이를 기준으로 정렬 
    ans.sort(key = lambda x: x[2])
    # 시작 인덱스와 마지막 인덱스만 반환
    return ans[0][:2]

 

🟡 sol2) start와 end를 직접 이동 

def solution(sequence, k):
        n = len(sequence)
        start, end, sum = 0, 0, sequence[0]
        ans = [0, float('inf')]
        
        while start <= end and end < n:
            # 1. 현재 수열의 합 < k
            # end += 1
            if sum < k and end < n-1: # end += 1 할 것이기에 범위 체크
                end += 1
                sum += sequence[end]
            
            # 2. 현재 수열의 합 > k
            # start += 1
            elif sum > k:
                sum -= sequence[start]
                start += 1
                
            # 3. 현재 수열의 합 == k
            elif sum == k:
                # 기존에 등록된 수열의 길이와 비교 
                # 같으면 인덱스 작은 것을 등록해야 하기에 갱신하지 않는다
                if ans[1] - ans[0] > end - start: 
                    ans = [start, end]
                
                # sum = k를 만족하는 더 짧은 수열이 있을 수 있기에 start += 1 
                sum -= sequence[start]
                start += 1
            
            # 4. (1, 2, 3) 조건을 만족하지 못했는데 end를 갱신하지 못해 무한루프인 경우 방지
            else:
                if end == n-1:
                    break
                
        return ans