[프로그래머스 / 연속된 부분 수열의 합 / JAVA]

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

프로그래머스

 

문제 접근

투 포인터?

두 개의 인덱스를 움직여가며 원하는 값을 탐색한다.

right부터 한 칸씩 움직여서 k가 만들어지거나 k를 넘기전까지 right의 인덱스를 차곡차곡 더한다.

k를 만들면 그 때의 left, right 인덱스를 저장 

k를 넘어가면 left 인덱스의 값을 삭제하고 left를 한 칸씩 움직인다.

이렇게 left, right를 동시에 움직이며 부분 수열 합이 k인 부분을 탐색한다.

k인 부분 수열이 여러개면 길이를 비교, 길이가 같다면 left 인덱스가 작은 값의 부분 수열을 저장

 

[참고한 방법] → 그림으로 잘 설명되어 있다.

https://ksb-dev.tistory.com/302

 

 

예전엔 이런 문제를 풀 때 만들 수 있는 모든 경우의 수를 다 비교했던 거 같은데 확실히 문제 유형을 숙지하고 있으면 접근하기 쉬울 거 같다.

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
	   
		int left = 0;
		int right = 0;
		int partSum = sequence[0]; // 처음엔 left, right 인덱스가 0이라
		int length = sequence.length;
		
		List<Integer> sub = new ArrayList<>();
		
		while(true) {
			
			// k와 같을 때의 인덱스 위치 저장
			if(partSum == k) {
				sub.add(left);
				sub.add(right);
			}
			
            // 부분 수열의 합이 k와 같은 게 여러 개면
			if(sub.size() == 4) { // 길이 더 작은 쪽 확인
				if(sub.get(1)-sub.get(0) < sub.get(3)-sub.get(2)) {
					sub.remove(2);
					sub.remove(2);
				}
				else if(sub.get(1)-sub.get(0) > sub.get(3)-sub.get(2)) {
					sub.remove(0);
					sub.remove(0);
				}
				else { // 길이도 같다면, 미리 저장된 인덱스가 더 작으니 뒤에 오는 인덱스 제거
					sub.remove(2);
					sub.remove(2);
				}
			}
			
			// 두 인덱스가 끝에 다다르면 정지
			if(left == length && right == length) break;
			
			// 부분 합이 k보다 작으면서 right 인덱스가 끝까지 가지 않으면 한 칸 씩 움직이기
			if(partSum <= k && right < length) {
				right++;
				
				// right가 수열을 벗어나지 않은 상태에서 right 1칸 움직인 값을 부분 수열에 합하기
				if(right < length) partSum += sequence[right];
			}
			
			// 부분 합이 k를 넘어가게 되면
			else {
				if(left < length) partSum -= sequence[left];
				left++;
			}
		}
		return new int[] {sub.get(0), sub.get(1)};
	}
}

 

다른 사람 풀이

비슷한 방식이라도 코드의 길이를 생각하기에 따라 많이 줄일 수 있다.

++right, left++ 처럼 진행 순서에 따라 바로 더해주거나 실행 후에 더해주거나

class Solution {
	public int[] solution(int[] sequence, int k) {

        int left = 0, right = -1, sum = 0;
        int length = 1000001, sLeft = 0, sRight = 0; 

        while (right < sequence.length) { // right 인덱스가 끝을 넘어가기 전까지

            if (sum < k) { // 부분 수열 합이 k보다 작다면
                if (++right < sequence.length) // right의 다음 좌표도 마지막 인덱스를 넘지 않았다면 
                    sum += sequence[right]; // right인덱스의 값 더하기
                
            } else if (k < sum) { // 부분 수열 합이 k를 넘어갔다면
                sum -= sequence[left++]; // left 좌표를 합에서 빼고 한 칸 움직이기
                
            } else { // 부분 수열 합이 k라면
                if (right - left < length) { // 길이만 비교해줘도 left 시작 인덱스를 비교해줄 필요 없다? → 길이가 같다면 제일 낮은 인덱스가 계속 들어가있기 때문
                    length = right - left; // k와 같을 때 right와 left의 차이를 length에 저장
                    sLeft = left;
                    sRight = right;
                }
                sum -= sequence[left++]; // k와 같더라도 이미 저장되있는 부분 수열의 길이보다 작지 않으면 left 한 칸 땡겨서 바로 진행
            }
        }
        return new int[] { sLeft, sRight };
    }
}