[투포인터, 정렬된 배열의 구간합] 프로그래머스 lv2. 연속된 부분 수열의 합

문제 : 연속된 부분 수열의 합

프로그래머스 문제 바로가기

 

 

조건 1.  오름차순으로 정렬된 배열
조건 2.  배열의 길이 ≤ 1,000,000
요구사항 : 
  구간합이 특정 값이 되었을 때, 구간의 인덱스를 반환하라
  단, 여러 구간이라면 길이가 짧은 구간을 채택하고, 길이마저 같다면 시작인덱스가 작은 구간을 채택하라.

접근

• 배열의 크기가 10^6이기 때문에 O(n^2) 알고리즘은 사용할 수 없다.
• 정렬된 배열의 특성을 최대한 이용한다.
• 구간합에 관한 문제이기 때문에 투포인터를 사용할 수 있다. (이진탐색은 특정 값을 찾는 데 사용)

내 풀이

def solution(sequence, k):
    sp = 0
    ep = 1
    tot = sequence[0]
    sequence+=[0]
    answer = []
    chance = 1

    while not(sp >= ep or ep == len(sequence)):
        if tot < k :
            tot += sequence[ep]
            ep += 1

        elif tot > k:
            tot -= sequence[sp]
            sp += 1

        elif tot == k:
            # 길이, 시작인덱스, 마지막인덱스
            arr = [ep-sp, sp, ep-1]
            if (not answer) or answer[0] > arr[0]:
                answer = arr
            elif answer[0] == arr[0] :
                answer = arr if answer[1] > arr[1] else answer
            tot -= sequence[sp]
            sp += 1

    return answer[1:]

개선한 풀이

def solution(sequence, k):
    sp, ep = 0, 1
    ans_sp, ans_ep = 0, 10**7
    part_sum = sequence[0]
    sequence += [0]

    while sp < ep < len(sequence):
        if part_sum < k :
            part_sum += sequence[ep]
            ep += 1

        elif tot == k and ans_ep-ans_sp > ep-sp :  # 길이가 큰 게 아니면 할당 안하고 넘어가게 됨, 
            ans_sp, ans_ep = sp, ep                            # 즉, 길이 동일하면 인덱스 큰 건은 할당 안하게 되면서
                                                                      # 자동으로 가장 작은 인덱스가 정답으로 남아있게 되는 것.
        else:
            tot -= sequence[sp]
            sp += 1


    return ans_sp, ans_ep-1

• 가독성을 위해, 변수 사용 방식을 바꿨다,
• 불필요한 배열 사용을 없애고, 변수 사용으로 변경했다.
• 조건문을 더 단순하게 만들었다.
  => 동일했을 때, 빠져나갈 방법이 없다고 생각했는데 else문 처리로 기본 액션을 시작인덱스(sp)를 이동시키는 걸로 해두니 해결됐다
  => 이렇게 하니, 특히 시작인덱스 크기를 비교하지 않아도 되게 되었다.