알고리즘 코드카타 109 - 연속된 부분 수열의 합

https://school.programmers.co.kr/learn/courses/30/lessons/178870?language=python3

프로그래머스

 

문제 설명
비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.

기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
부분 수열의 합은 k입니다.
합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.
수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

 

제한사항
5 ≤ sequence의 길이 ≤ 1,000,000
1 ≤ sequence의 원소 ≤ 1,000
sequence는 비내림차순으로 정렬되어 있습니다.
5 ≤ k ≤ 1,000,000,000
k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.

 

 

가장 먼저 떠올린 방법은 부분수열중 원소들의 합이 7인 경우를 찾아서 길이가 더 짧을 경우를 갱신하면서 부분수열의 인덱스를 반환하는 것이었다.

하지만 부분수열의 원소들의 합을 구할 때, sum()을 사용한다면 매 반복마다 sum()연산을 반복하게 되기 때문에 실행시간이 상당히 더뎌질 것이다. 그래서 이전에 사용했던 방법처럼 부분 수열의 합을 변수로 지정해서 지속적으로 변동시킬 생각이다.

부분수열의 인덱스도 마찬가지이다. 부분수열이 변동될 때마다 기존수열에서 현재 부분수열의 인덱스를 반환하기보다는 시작인덱스와 끝인덱스를 변수로 지정해두고 지속적으로 변동시켜서 인덱스의 위치를 기록할 생각이다.

def solution(sequence, k):
    start = 0
    end = 0
    sub_seq = deque()
    sum_sub_seq = 0
    current_len = float('inf')
    
    for seq in sequence:
    	sum_sub_seq += seq
        sub_seq.append(seq)
        end += 1
        while sum_sub_seq + seq > k and sub_seq:
            sum_sub_seq -= sub_seq[0]
            sub_seq.popleft()
            start += 1

 

부분수열의 시작 인덱스와 끝 인덱스를 각각 start와 end라는 변수에 할당하고 현재 부분수열을 sub_seq 그 부분수열의 합은 sum_sub_seq에 할당했다.

 

for 반복문을 통해서 sequence의 모든 원소를 순회하면서 다음과 같은 과정을 반복한다.

1. 현재 원소인 seq를 sum_sub_seq에 더하고 sub_seq에 추가한다. 이것은 부분수열과 부분수열의 합을 업데이트 하는 과정이다.

2. 수열의 길이가 늘어났으므로 end를 증가시켜서 부분수열이 기존수열에서 가지는 인덱스를 설정한다.

3. 현재 부분수열의 합과 기존수열의 다음 원소를 더한 값이 목표값 k 보다 클 경우(즉, 현재 부분 수열로 목표한 값을 만들 수 없을 경우)에 다음 과정을 반복한다.(단, sub_seq에 원소가 존재할 경우에만 작동한다.)

    1) sum_sub_seq에서 sub_seq의 가장 앞에 있는 값을 빼고 sub_seq에서 제거한다. 이것은 부분수열의 시작 인덱스를 당겨오는 과정이다.

    2) 부분수열의 시작 인덱스가 변동됐으므로 현재 위치를 반환한다.

    3) 이 과정을 sum_sub_seq에 다음 원소를 더해도 k보다 작아질 때까지 반복한다.

 

여기까지 작성을 하고 중간과정을 확인하기 위해 실행을 해보았는데 생각처럼 잘 작동하지 않았다. 문제는 두가지였다.

1. 부분 수열의 끝 인덱스은 end가 예상보다 크게 출력되었다.

2. while반복문이 제대로 작동하지 않았다.

 

다행히 두 문제 모두 쉽게 해결할 수 있었다. 1의 경우 end가 0부터 시작하는 것이 문제였다. 파이썬의 리스트의 인덱스는 [시작값, 끝값-1]로 나타나기 때문이다. end = -1이라고 다시 설정해서 해결할 수 있었다.

2번의 경우 원래 목적은 현재 sum_sub_seq에 다음 seq값이 더해지기 전에 목표값보다 크다면 seq를 더할 수 있도록 그만큼 값을 줄여주는 것이었다. 그런데 위와같은 순서로 함수가 작동한다면 이미 더한 수를 한번 더 더한 값을 k와 비교한다는 문제가 있었다. 따라서 위의 구문과 자리를 바꿔서 seq가 더해지기 전의 값과 비교를 해서 반복문이 작동할 수 있도록 수정했다.

def solution(sequence, k):
    start = 0
    end = -1
    sub_seq = deque()
    sum_sub_seq = 0
    
    for seq in sequence:
        while sum_sub_seq + seq > k and sub_seq:
            sum_sub_seq -= sub_seq[0]
            sub_seq.popleft()
            start += 1
        sum_sub_seq += seq
        sub_seq.append(seq)
        end += 1

 

이제 여기까지는 정상적으로 작동이 된다.

 

def solution(sequence, k):
    start = 0
    end = -1
    sub_seq = deque()
    sum_sub_seq = 0
    current_len = float('inf')
    
    for seq in sequence:
        while sum_sub_seq + seq > k and sub_seq:
            sum_sub_seq -= sub_seq[0]
            sub_seq.popleft()
            start += 1
        sum_sub_seq += seq
        sub_seq.append(seq)
        end += 1
        if sum_sub_seq == k:
            if (end - start) < current_len:
                current_len = end - start
                min_start = start
                min_end = end
                
    return [min_start, min_end]

 

다음으로 반복문의 끝에 조건문을 추가해서 sum_sub_seq가 목표값 k와 같을 경우 인덱스값을 저장하도록 했다. current_len에 현재 저장된 인덱스의 값을 저장해서 조건에 맞는 부분수열의 길이가 current_len보다 짧을 경우 current_len값을 포함해서 현재 인덱스의 값으로 업데이트해준다.

 

이 방법으로 테스트케이스는 모두 통과할 수 있었다. 하지만 정답을 제출했을 때, 예상대로 문제가 발생했다.

시간초과!

 

당연하다면 당연한 문제였다. 다행히 이번에는 해결방법을 알고있다.

https://youtharchive.tistory.com/48

알고리즘 코드카타 106 - 택배상자

이때에도 지금과 비슷하게 리스트조작에 실행시간이 오래걸렸었기 때문이다. 그때와 마찬가지로 자료의 구조형을 deque로 바꿔주었다.

from collections import deque

def solution(sequence, k):
    start = 0
    end = -1
    sub_seq = deque()
    sum_sub_seq = 0
    current_len = float('inf')
    
    for seq in sequence:
        while sum_sub_seq + seq > k and sub_seq:
            sum_sub_seq -= sub_seq[0]
            sub_seq.popleft()
            start += 1
        sum_sub_seq += seq
        sub_seq.append(seq)
        end += 1
        if sum_sub_seq == k:
            if (end - start) < current_len:
                current_len = end - start
                min_start = start
                min_end = end
                
    return [min_start, min_end]

당연히 성공!

 

이전에 비슷한 경우를 겪어보았던 경험이 도움이 되었다.