연속된 부분 수열의 합
문제 설명
비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.
- 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
- 부분 수열의 합은 k입니다.
- 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
- 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.
수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.
시각화
[1, 2, 3, 4, 5] 의 수열이 주어졌을 때 k = 7 일 경우 아래와 같이 부분 수열을 찾을 수 있다.
문제 해결 과정
우선 비내림차순이 무엇인지 알아보자.
오름차순과 내림차순은 매우 익숙하나 비내림차순은 처음 들어본 용어였다. 비내림차순은 오름차순과 유사한데 차이점은 중복된 값이 있을 수 있다는 것이다. 데이터베이스에서 오름차순, 내림차순이 익숙하다보니 혼용을 하고 있었던 것 같다. 엄밀히 따지면 오름차순은 중복된 값이 없어야 한다.
문제로 돌아와서 보면 비내림차순으로 정렬된 수열이라는 것은 중복된 값이 있을 수 있는 오름차순이라는 것이다. 이를 요약하면 뒤로 갈수록 값이 커지는 수열이라는 것이다.
이 문제는 two-pointer 를 사용하여 풀 수 있다. 좌우 간격을 두고 합을 계산하면서 k 보다 작으면 우측으로 이동하고 k 보다 크면 좌측으로 이동하면 된다.
left 와 right 을 각각 0으로 두고 시작을 하면서 현재 값이 k 보다 작으면 right 을 증가시키고 k 보다 크면 left 를 증가시킨다.
1, 2, 3 을 다 더해도 7 보다 작기에 right 를 증가시킨다.
1, 2, 3, 4 가 되니 10 이 되었기에 left 를 증가시킨다.
left 가 증가되면서 3, 4 가 되었다. 바로 return 을 하면 안되는 이유는 뒤에 더 작은 수열의 조합이 있을 수 있기 때문이다.
right 를 늘리면서 위와 같은 과정을 반복한다.
전체 코드
위 논리를 코드로 적으면 아래와 같다.
def solution(sequence, k):
answer = []
l, r = 0, 0
v = sequence[0]
while r < len(sequence):
if r < l:
break
if v == k:
if not answer:
answer = [l, r]
else:
if r - l < answer[1] - answer[0]:
answer = [l, r]
v -= sequence[l]
l += 1
if v < k:
if r >= len(sequence) - 1:
break
r += 1
v += sequence[r]
if v > k:
v -= sequence[l]
l += 1
return answer
print(solution([1], 1)) # [0, 0]
print(solution([1, 2, 3, 4, 5], 7)) # [2, 3]
print(solution([1, 1, 1, 2, 3, 4, 5], 5)) # [6, 6]
print(solution([2, 2, 2, 2, 2], 6)) # [0, 2]
