서론
오늘의 코딩 테스트 문제는 '연속된 부분 수열의 합'이다. 프로그래머스 Level 2 문제로, 투 포인터 알고리즘을 활용하면 효율적으로 해결할 수 있는 문제다.
문제 개요
오름차순으로 정렬된 수열에서 합이 k인 부분 수열 중 가장 짧은 것을 찾는 문제다. 길이가 같은 수열이 여러 개라면 시작 인덱스가 작은 것을 선택한다.
주요 제한사항:
•
5 ≤ sequence의 길이 ≤ 1,000,000
•
1 ≤ sequence의 원소 ≤ 1,000
•
5 ≤ k ≤ 1,000,000,000
접근 방식
1.
투 포인터 알고리즘 사용
2.
좌우 경계선(start, end)을 이동하며 부분 합 계산
3.
부분 합이 k와 같을 때마다 최소 길이 갱신
4.
모든 경우의 수를 확인하기 위해 끝까지 탐색
코드
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> sequence, int k) {
vector<int> answer = {0, 1000000};
int s=0, e=0, acc=sequence[0];
while (s<sequence.size() && e<sequence.size())
{
if (acc==k)
if ((answer[1]-answer[0])>(e-s))
answer = {s, e};
// 한칸 앞으로 줄이는게 k에 가까워지면
if (abs(k-acc)>abs(k-(acc-sequence[e])))
acc = acc - sequence[--e];
// 한칸 뒤까지 더하는게 k에 가까워지면
else if (abs(k-acc)>abs(k-(acc+sequence[e+1])))
acc = acc + sequence[++e];
// 현재가 최상의 상태이면
else
acc = acc - sequence[s++];
}
return answer;
}
C++
복사
구현 과정
1.
start와 end 포인터 초기화
2.
현재 부분 합(acc) 계산
3.
acc와 k 비교:
•
acc == k: 길이 비교 후 정답 갱신
•
acc > k: start 포인터 이동
•
acc < k: end 포인터 이동
4.
포인터가 배열 끝에 도달할 때까지 반복
회고
이 문제는 난이도가 높지 않았지만, 예상보다 시간이 많이 걸렸다. 최근 투 포인터 유형의 문제에서 자주 시간을 낭비하는 것 같다.
개선점:
1.
투 포인터 알고리즘 문제 유형 추가 학습 필요
2.
edge case 처리에 더 주의를 기울일 것
3.
시간 복잡도를 먼저 고려하여 접근 방식 결정하기
