문제

https://school.programmers.co.kr/learn/courses/30/lessons/178870

풀이

오름차순 수열에서 연속되는 수들의 합이 k가 되는 범위를 찾는 문제이다.

여기서 추가 조건이 있다.
1. 합이 k인 부분 수열이 여러 개라면 길이가 짧은 수열을 찾는다.
2. 길이가 짧은 수열이 여러 개라면 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾는다.

이 문제를 처음 보고 deque를 떠올렸다. 원소를 하나씩 추가하다가 만약 sum이 k를 넘는다면 오래된 순으로 원소를 삭제한다.

sum이 k를 넘는 한 우리가 필요로 하는 sum == k인 상황을 만들 수 없기 때문이다.

이후 sum은 k와 같거나 작게 되는데 우리가 필요한 것은 sum == k일 때이므로 sum == k 일 때 이전 length의 최솟값보다 현재 배열의 길이가 더 작다면 시작 지점과 끝 지점의 정보를 갱신해준다.

이 풀이에 대한 코드는 다음과 같다.

import java.util.Deque;
import java.util.LinkedList;

class Solution {
   public int[] solution(int[] A, int k) {	        
	        int N = A.length;
	        
	        int s = 0,e= 0, minCnt = N + 1;
	        int sum = 0;
	        Deque<Integer> dq = new LinkedList<>();
	        for(int i = 0 ; i <N ; i++) {
	        	sum += A[i];
	        	dq.addLast(i);
	        		        	
	        	
	        	while(sum > k) {
		        	int idx = dq.getFirst();
		        	sum -= A[idx];
		        	dq.removeFirst();
	        	}
	        	
	        	if(sum == k) {
	        		if(minCnt > dq.size()) {
	        			minCnt = dq.size();
	        			s = dq.getFirst();
	        			e = dq.getLast();
	        		}
	        	}
	        }
	
	        int[] answer = {s,e};	        
	        return answer;
	    }
}

문제를 풀고 다른 사람 풀이를 보니 더 쉬운 풀이가 있었다. 바로 투 포인터이다.

이전 풀이는 원소들을 deque에 넣었지만 사실 연속된 수열의 값을 구하는 것이므로 시작 지점과 끝 지점의 index만 가지고 구할 수 있다.

이 때 주의해야 할 점은 left와 right의 범위이다. left = 0, right = -1을 초기값으로 설정하고 right가 수열의 끝을 넘어가기 전까지 반복을 수행한다.

부분 수열 합이 k보다 작다면 right 값을 더해야 하는데 ++right했을 때 끝을 넘어갔는 지에 대한 검사가 필요하다.

초기 조건 설정 외에 이전 풀이와 유사하다.

코드

public int[] solution(int[] sequence, int k) {	        	       
	        int[] answer = new int[2];
	        
	        int n = sequence.length;
	        int minLength = n + 1;
	        int l = 0, r = -1;
	        int sum = 0;
	        
	        while(r < n) {
	        	if(sum < k) {
	        		if(++r < n) { // r 증가 후 범위 체크
	        			sum += sequence[r];
	        		}
	        	}
	        	else if(sum == k) {
	        		if(minLength > r - l + 1) {
	        			minLength = r - l + 1;
	        			answer[0] = l;
	        			answer[1] = r;
	        		}
	        		sum -= sequence[l++];
	        	}
	        	else {
	        		sum -= sequence[l++];
	        	}
	        }	        
		               	     	        
	        return answer;
	    }