Programmers / 연속된 부분 수열의 합 / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 연속된 부분 수열의 합 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

def solution(sequence, k):
    answer = []

    idx = 0

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

    while idx < len(sequence):
        result = 0
        for j in range(idx, len(sequence)):
            result += sequence[j]
            if result > k:
                break
            elif result == k:
                return [idx, j]
        idx += 1

    return answer

 

처음 풀이에는 입출력 예 #2 경우처럼 시작 인덱스와 마지막 인덱스 길이가 같은 경우를 제외하면 하나씩 비교해나가면서 검사하는 것이 정답일 줄 알았다. sequence의 원소도 1000개라서 1000*1000 정도의 크기니깐 어느 정도 될 것 같았는데 틀렸다.

 

def solution(sequence, k):
    l = 0 
    r = 0
    answer = [0, len(sequence)]
    sum = sequence[0]

    while True:
        if sum < k:
            r += 1
            if r == len(sequence): 
                break
            sum += sequence[r]
        else:
            if sum == k:
                if r - l < answer[1] - answer[0]:
                    answer = [l, r]
            sum -= sequence[l]
            l += 1
    return answer

 

두 번째 풀이는 왼쪽과 오른쪽의 범위를 지정해서 만약에 범위 안에 들어가 있는 값들이 sum == k와 같다면 멈추고 값을 반환했다.

---

※ 알아야 할 것

 

반복문을 두 번 사용하지 않는 풀이법을 찾는 것이 중요하다.