[프로그래머스] 연속된 부분 수열의 합 Python 풀이

📘 문제

플랫폼: 프로그래머스
난이도: Lv2
유형: 구현

 

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/178870

코딩테스트 연습 - 연속된 부분 수열의 합

 

주어진 배열에서 연속된 수열의 합이 k가 되는 경우를 구한다.

여러 개일 경우 길이가 짧은 것, 똑같은 길이가 여러 개인 경우 앞쪽에 있는 수열의 시작 인덱스와 끝 인덱스를 return 하는 문제

 

 

 

🧠 접근 방법 및 풀이 과정

나는.. 효율성 문제에 약하다...ㅠ

 

막 구현으로 테케 맞춘 1차 코드

i, j를 포인터 역할로 두고 조건에 부합하는 모든 수열 경우를 구한 뒤,

적절한 답을 찾아내는 방식으로 했다

제출 후 10개 중에 4번까지 힘겹게 성공..

 

def solution(sequence, k):
    answer = []
    
    i = 0
    j = 0
    
    candidates = []
    
    while i < len(sequence):
        total = 0
        
        for v in sequence[i:j+1]:
            total += v
            
        if total == k:
            candidates.append([i, j])
        
        if j >= len(sequence) - 1: 
            i += 1
            j = i
            continue
            
        j += 1
    
    l = len(sequence)
    for i, j in candidates:
        if j - i == l:
            continue
        elif j - i < l:
            l = j - i
            answer = [i, j]
        
    return answer

 

2번째 시도

코드 길이를 7줄로 줄였고 5번까지 성공했지만 이번에도 실패 ㅠㅠ

합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열, 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾아야 하므로 길이가 짧은 순부터 긴 방향으로, 시작 인덱스가 작은 경우부터 큰 경우로 가도록 반복문을 돌면서 합이 k인 경우 정답을 바로 제출하도록 했다

 

그런데 이렇게 해도 실패 할 수 밖에 없는게 O(N^3) 시간 복잡도이기 때문이다

def solution(sequence, k):
    l = len(sequence)
    
    for r in range(l):
        for i in range(l):
            if sum(sequence[i : i + r + 1]) == k:
                return [i, i + r]

 

3번째 시도

테케 1번을 예시로 들면

r = 1
[3, 0, 0, 0, 0] i = 0, j = 1
[3, 5, 0, 0, 0] i = 1, j = 2
[3, 5, 7, 0, 0] i = 2, j = 3
[3, 5, 7, 9, 0] i = 3, j = 4
r = 2
[6, 5, 7, 9, 5] i = 0, j = 2
[6, 9, 7, 9, 5] i = 1, j = 3
[6, 9, 12, 9, 5] i = 2, j = 4
r = 3
[6, 9, 12, 9, 5] i = 0, j = 3

 

이런 식으로 배열을 갱신 했을 때 k가 나오면 인덱스쌍을 return 해주도록 했다

def solution(sequence, k):
    if k in sequence: return [sequence.index(k), sequence.index(k)]

    i = 0
    j = 1
    r = 1
    
    cum_list = [ele for ele in sequence]
    
    while r < len(sequence):
        cum_list[i] = cum_list[i] + sequence[j]
        
        if cum_list[i] == k:
            return [i, j]
        
        i += 1
        j += 1
        
        if j == len(sequence):
            r += 1
            i = 0
            j = r

 

그러나 이것도 실패,, 히히,,

 

 

결국 GPT의 도움을 받았다

 

 

 

💻 코드 & 설명

def solution(sequence, k):
    left = 0
    total = 0
    answer = []
    min_len = len(sequence) + 1

    for right in range(len(sequence)):
        total += sequence[right]

        while total > k:
            total -= sequence[left]
            left += 1

        if total == k:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                answer = [left, right]

    return answer

 

 

✨ 회고 / 느낀 점

레벨 2인데 이 문제 꽤나 어려운걸..? ㅠㅠ

 

💭 질문하기와 다른 사람의 풀이를 보니 누적합 또는 투포인터로 많이 푼 것 같다. 구현 + 효율성 문제 계속 연습!!!!

 

AI가 생성한 이미지