8/6 Coding Test

✅ Programmers

🎈 연속된 부분 수열의 합

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

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 한다.
• 부분 수열의 합은 k이고 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열 찾기
• 길이가 짧은 수열이 여러 개인 경우 앞쪽에 나오는 수열 찾기
  입력값으로 sequence (수열)과 부분 수열의 합 k가 주어질 때 위 조건을 만족하는 부분 수열의 시작 인덱스와 끝 인덱스를 배열에 담아 리턴하는 문제
• sequence 길이 : [5, 1,000,000], k의 범위 : [5, 1e9]

def solution(sequence, k):
    answer = []
    start = 0
    end = 0
    n = len(sequence)
    total = 0

    while True:
        if total <= k:
            if total == k:
                answer.append([start,end-1])
            if end >= n:
                break
            total += sequence[end]
            end += 1
        else:
            total -= sequence[start]
            if start >= n:
                break
            start += 1
    answer.sort(key=lambda x:(x[1]-x[0], x[0]))
    return answer[0]

< 풀이 과정 >

• start, end 로 인덱스 값을 0으로 우선 지정한다.
• total 변수로 0을 지정하여 sequence 배열 내 값들을 순차적으로 저장한다.

이후 while 문으로 반복을 진행하되 다음 과정을 반복해준다

• total 값이 k보다 작거나 같다면, end (끝 인덱스 범위를 늘려주어야 한다.) 이때, total과 k가 같다면 시작 인덱스와 끝 인덱스-1을 answer 배열에 저장한다. 그 후 total 값에 sequence배열 내 end 인덱스 위치에 값을 추가해준다.
• total 값이 k보다 크다면, total 값에서 sequence 배열 내 start 인덱스에 위치한 값을 빼준다.

이 과정에서 start, end 변수가 주어진 범위를 벗어나는 경우 while 문을 중단한다.

최종적으로 길이가 짧은 수열 (x[1] - x[0]), 시작 인덱스가 가장 앞쪽인 경우 (x[0])을 sorting하여 answer의 제일 첫번째 위치한 리스트를 출력한다.