문제:
출처: 프로그래머스 - 연속된 부분 수열의 합
문제 설명
비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.
기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
부분 수열의 합은 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의 부분 수열로 만들 수 있는 값입니다.
풀이:
포인트 : 비내림차순, 길이가 1,000,000
1. 길이가 1백만이라서 빅오 표기법에 따라서 O(N)이 되도록 한다. 이중 반복문처럼 코드의 연산이 O(N^2)이 되면 안된다. 예로 투 포인터를 기준으로 슬라이싱한 합, sum(sequence[lt:rt])을 할 때, k값이 크고 sequenced의 값이 작아서 슬라이싱한 길이가 길다면 O(N^2)의 연산이 필요해진다. 길이의 합을 구할 누적값 변수를 선언한다.
2. 양 구간을 인덱스 값 lt, rt로 설정하고 구간의 값이, 구하려는 값 k보다 작으면 rt를 더해서 누적 값을 올리고 구하려는 값 k보다 크다면 lt를 올려주고 lt값 만큼 누적값에서 빼준다.
3. 누적값이 구하려는 값 k와 같을 때 길이가 작은 값을 구해야함으로 'rt - lt + 1'(인덱스 길이 값)이 더 짧은 구간일 때에만 업데이트 하도록 해준다.
코드:
def solution(sequence, k):
answer = []
n = len(sequence) # 전체 길이
minN = 1e9
lt = 0
rt = 0
sumN = sequence[0] # 누적값 선언
while lt <= rt < n: # 전체 길이에서 인덱스 값이 벗어나면 반복분 중단.
# 컷 부분
if sequence[rt] == k: # 한 인덱스의 값이 찾는 값과 같다면 가장 짧은 길이이므로 바로 결과 출력, 또한 오름차순이기에 뒤는 더 볼 필요가 없다.
answer = [rt, rt]
return answer
if sequence[rt] > k: #오름차순으로 정렬이 되었기에 k보다 큰 값이 있다면 그 뒤는 더 볼 것 없이 k보다 큰 수 이므로 바로 함수를 리턴한다.
return answer
# 진행부분
if sumN == k: # 누적값이 찾을려는 값과 일치할 때
if minN > rt - lt + 1: # 길이가 짧은 구간의 값을 업데이트하도록 한다.
minN = rt - lt + 1
answer = [lt, rt]
sumN -= sequence[lt] # 더 짧은 길이가 찾기 위해 다시 진행하도록 한다. 누적값을 빼고
lt += 1 # 왼쪽 인덱스를 올린다.
elif sumN < k: # 누적값이 찾는 값보다 작으므로 계속 누적값을 더한다.
rt += 1
if rt < n: # rt가 끝지점에 왔을 때 에러를 방지하기 위해(끝지점 + 1의 값은 없으므로 누적할 때 에러가 난다)
sumN += sequence[rt]
else: # 누적값이 크다면 k보다 크다면 lt의 값을 누적값에서 뺀다.
sumN -= sequence[lt]
lt += 1
return answer