[programmers] 연속된 부분 수열의 합

오늘 스터디 발표를 가장한 스터디원 모임을 가졌다.

재미있었다. ㅋㅋㅋ

그래도 문제는 푼다.

프로그래머스 Lv.2 연속된 부분 수열의 합

문제 분석
주어진 배열 sequence에서 부분 수열의 합이 k가 되는 경우,
1. 부분 수열의 길이가 짧고
2. 길이가 짧은 수열이 여러개라면 가장 앞에 나온 수열을
출력한다.

입출력 예 #2

[1, 1, 1, 2, 3, 4, 5]에서 합이 5인 연속된 부분 수열은 
[1, 1, 1, 2], [2, 3], [5]가 있습니다. 
이 중 [5]의 길이가 제일 짧으므로 해당 수열의 시작 인덱스와 
마지막 인덱스를 담은 [6, 6]을 반환합니다.

첫 번째 코드

def solution(sequence, k):
    answer = []
    idx = 0
    if k in sequence:
        a = sequence.index(k)
        return [a,a]
  
    while True:
        if idx == len(sequence):
            break
        checker = 0   
        for i in range(idx,len(sequence)):
            checker += sequence[i]
            if checker > k:
                break
            if checker == k:
                if not answer:
                    answer = [idx,i]
                else:
                    if answer[1]-answer[0] > i-idx:
                        answer = [idx,i]
        idx += 1
         
    return answer

기본적인 아이디어는,

1. 시작 index를 기준으로 탐색한다. 
2. 부분수열의 합이 k가 될때까지 계속 더해서
2-1. k를 넘으면 반복문 처음으로 
2-2. k와 같아지면 해당 부분수열의 index를 저장한다.
3. 시작 index를 1씩 증가시키면서 더 짧은 부분수열이 있다면
   answer을 변경해준다.

논리 자체는 잘 세웠다.

하지만 효율성에 문제가 있다.
새 아이디어가 필요하다.

두 번째 코드

def solution(sequence, k):
    answer = []
    if k in sequence:           # 1개짜리가 있는경우
        a = sequence.index(k)
        return [a,a]
  
    length = 2 # 1개인 경우는 위에서 끝났음.
    while length <= len(sequence):
        # length개의 합 중에 만족하는 게 있는지 체크한다.
        for i in range(0,len(sequence) - length+1): 
        # 탐색을 시작할 index
            if sum(sequence[i:i+length]) == k:
                return [i,i+length-1]
        
        length += 1

이번에는 index가 아니라 부분수열의 길이를 기준으로 탐색했다.

또 안된다.
역순으로 해도 안된다.
아예 다른 방법을 찾아야 한다.
수학적 논리가 필요하거나, DP로 풀 아이디어가 필요하다.

도저히 안되겠다. 자고 일어나서 풀자.

지금 코드의 시간복잡도는 $O(n^2)$이다.
for loop내에서 sum함수가 호출되기 때문인데,
다른 방법을 찾아야 하는 것이다.

sum함수를 호출하지 않고 풀 수 있는 수학적 논리를 찾았다.

수학적 아이디어

1. 인덱스의 누적 합계와 부분수열의 합 사이에 관계가 있다.
2. 예시 리스트 [1,2,3,4] => 1,3,6,10
3. 6-1(idx(2)-idx(0) = 5 = 2+3(idx(1)+idx(2))
4. 10-1(idx(3)-idx(0)) = 9 = 4+3+2(idx(1)+...+idx(3))
5. (A1+A2+A3+...+Am) - (A1+A2+...+An)
   = Am+1+Am+2+...+An

그러니까 이런 수학적 관계가 있는 것이다.
5. 누적합계배열의 두 index n,m에 대하여,
   arr[m]-arr[n]은 n+1번째부터 m번째까지의 부분합과 같다.

좋다 이걸로 코드를 바로 짜보자.
이번엔 되겠지 코드

## 논리는 다 짰으므로, 주석 부분은 제거하고 코드만 올린다.

def solution(sequence, k):
    answer = []
   
    sigma = [0] # sigma연산 수행을 위한 초기값
    for i in sequence:
        sigma.append(sigma[-1]+i)

    n, m = 0, 0
    while n < len(sigma) and m < len(sigma):
        if sigma[m] - sigma[n] == k:
            if m-n-1 == 0:
                return [n,m-1]
            if not answer:
                answer = [n, m-1]
            if answer[1]-answer[0] > m-n-1:
                answer = [n, m-1]
            n += 1
        elif sigma[m] - sigma[n] < k:
            m += 1
        else:
            n += 1
            if n > m:
                m = n

    return answer

논리를 짜놓고 간단할 것으로 생각했는데,
탈출조건을 설정하는 것도 살짝 쉽지 않은 문제였다.

아..... 결국 이 코드도 $O(n^2)$ 인 것이었다.

이제는 아예 sigma 구성 자체를 미리 해주지 말고,
더하고 빼면서 직접 탐색하는 방법이 마지막 생각나는 방법이다.

아이디어

1. 먼저 sequence[0] == k이면 즉시 [0,0]을 return하고 종료한다.
2. c가 아직 k보다 작으면,
   1) 오른쪽 포인터를 1 증가시키고, c에 해당 인덱스의 값을 더한다.
3. c가 k보다 크거나 같으면,
   1) 왼쪽 포인터를 1 증가시키고, c에서 이전 인덱스의 값을 뺀다.
4. 탐색 과정에서 c == k이면,
   1) n==m이면 반드시 정답이 되므로 즉시 return한다.
   2) answer가 아직 선언되지 않았으면 [n,m]을 선언한다.
   3) 선언된 값이 있으면 문제 조건에 의해 answer을 최신화한다.

＠ 이때 탐색 방식이 0,0부터 탐색하기 때문에, 가장 먼저 발견된 좌표를 자동으로 return할 것이므로 문제의 마지막 조건은 자동으로 만족하는 답이 나올 것이다.

찐막 코드 - 못풀면 답보러간다.

def solution(sequence, k):
    answer = []
    n, m, c = 0, 0, sequence[0]
    while n < len(sequence) and m < len(sequence):
        if c == k:
            if n == m:
                return [n,m]
            else:
                if not answer:
                    answer = [n,m]
                else:
                    if answer[1]-answer[0] > m-n:
                        answer = [n,m]
  
        if c < k:
            m += 1
            if m == len(sequence):
                break
            c += sequence[m]
        else:
            n += 1
            if n == len(sequence):
                break
            c -= sequence[n-1]
 
    return answer

무려 4가지 방법으로 시도하였다.
힘들었다.