연속된 부분 수열의 합
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
성능 요약
메모리: 79.2 MB, 시간: 0.02 ms
문제 설명
비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.
- 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
- 부분 수열의 합은
k입니다. - 합이
k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다. - 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.
수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.
제한사항
- 5 ≤
sequence의 길이 ≤ 1,000,000- 1 ≤
sequence의 원소 ≤ 1,000 sequence는 비내림차순으로 정렬되어 있습니다.
- 1 ≤
- 5 ≤
k≤ 1,000,000,000k는 항상sequence의 부분 수열로 만들 수 있는 값입니다.
입출력 예
| sequence | k | result |
|---|---|---|
| [1, 2, 3, 4, 5] | 7 | [2, 3] |
| [1, 1, 1, 2, 3, 4, 5] | 5 | [6, 6] |
| [2, 2, 2, 2, 2] | 6 | [0, 2] |
입출력 예 설명
입출력 예 #1
[1, 2, 3, 4, 5]에서 합이 7인 연속된 부분 수열은 [3, 4]뿐이므로 해당 수열의 시작 인덱스인 2와 마지막 인덱스 3을 배열에 담아 [2, 3]을 반환합니다.
입출력 예 #2
[1, 1, 1, 2, 3, 4, 5]에서 합이 5인 연속된 부분 수열은 [1, 1, 1, 2], [2, 3], [5]가 있습니다. 이 중 [5]의 길이가 제일 짧으므로 해당 수열의 시작 인덱스와 마지막 인덱스를 담은 [6, 6]을 반환합니다.
입출력 예 #3
[2, 2, 2, 2, 2]에서 합이 6인 연속된 부분 수열은 [2, 2, 2]로 3가지 경우가 있는데, 길이가 짧은 수열이 여러 개인 경우 앞쪽에 나온 수열을 찾으므로 [0, 2]를 반환합니다.
문제 풀이
sequence 배열은 비내림차순으로 정렬되어 있고, 임의의 두 인덱스 사이의 원소의 합을 구해야하기 때문에 정렬을 사용하지 않았습니다.
sequence 배열의 원소는 양의 정수로만 이루어져있기 때문에 투 포인터를 포인터 사이의 누적합을 구해서 풀 수 있습니다.
예를 들어 sequence가 [1, 1, 1, 2, 3, 6, 5]이고, k 가 6일 때 투 포인터 동작 과정은 위의 그림과 같습니다.
투 포인터로 사용할 lt, rt를 0으로 초기화하고 가장 짧은 길이인지를 비교할 ptrLen을 최댓값으로 초기화합니다.
이후 누적합을 저장해가며, 누적합이 K보다 작으면 누적합을 증가시켜야 하기 때문에 rt만 증가시키고, 누적합이 K보다 크면 lt만 증가시킵니다.
누적합이 K와 같은 경우 현재 저장된 가장 짧은 원소 간 길이보다 짧은 지를 비교하고, 짧으면 정답 배열에 저장합니다. 이때 lt와 rt가 같다면 길이가 이후에 생길 수 있는 정답 원소들보다 짧으므로 순회를 종료하고 정답을 출력합니다.
자바 코드
import java.util.*;
class Solution {
public int[] solution(int[] sequence, int k) {
// 투 포인터 (lt, rt), 누적합 (sum), 현재 포인터 간 길이 (ptrLen) 초기화
int lt = 0;
int rt = 0;
int ptrLen = Integer.MAX_VALUE;
int sum = 0;
int[] answer = new int[2];
while (rt < sequence.length && lt <= rt) {
// 첫 번째 접근 또는 rt가 바라보는 원소가 k와 같을 때
if (lt == rt) {
sum = sequence[lt];
}
// 현재 누적합이 k와 같은 경우
if (sum == k) {
// 현재 포인터 간 길이가 이전 포인터 간 길이보다 짧은 경우
if (ptrLen > rt - lt + 1) {
ptrLen = rt - lt + 1;
answer[0] = lt;
answer[1] = rt;
}
// 모든 원소는 양수이기 때문에 다음 경우의 수를 찾기 위해 lt를 증가 시킬 것이며, 누적합 계산을 위해 현재 sequence[lt] 값을 빼준다.
sum -= sequence[lt];
// rt도 마찬가지로 증가시킬 것이기 때문에 현재 누적합에 sequence[rt + 1]을 더해준다.
if (rt + 1 < sequence.length) {
sum += sequence[rt + 1];
}
// 두 포인터가 같은 경우 가장 짧은 길이이기 때문에 순회를 종료
if (lt == rt) {
break;
}
// 각 포인터 증가
lt++;
rt++;
} else if (sum > k) {
// 누적합이 k 보다 큰 경우 lt를 증가해가며 k와 같은 지를 비교
sum -= sequence[lt];
lt++;
} else if (sum < k) {
// 누적합이 k 보다 작은 경우 rt를 증가해가며 k와 같은 지를 비교
if (rt + 1 < sequence.length) {
sum += sequence[rt + 1];
}
rt++;
}
}
return answer;
}
}
자바스크립트 코드
function solution(sequence, k) {
let answer = [];
let lt = 0;
let rt = 0;
let ptrLen = 1000001;
let sum = 0;
answer[0] = lt;
answer[1] = rt;
while ( rt < sequence.length && lt <= rt) {
if (lt == rt) {
sum = sequence[lt];
}
if (sum == k) {
if (ptrLen > rt - lt + 1) {
ptrLen = rt - lt + 1;
answer[0] = lt;
answer[1] = rt;
}
sum -= sequence[lt];
if (rt + 1 < sequence.length) {
sum += sequence[rt + 1];
}
if (lt == rt) {
break;
}
lt++;
rt++;
} else if (sum > k) {
sum -= sequence[lt];
lt++;
} else if (sum < k) {
if (rt + 1 < sequence.length) {
sum += sequence[rt + 1];
}
rt++;
}
}
return answer;
}
