[프로그래머스] 연속된 부분 수열의 합 Lv2 JAVA [투포인터][엄탱]

문제 링크

프로그래머스

문제 설명

자세한 문제는 링크를 통해서 확인하면 된다.

비내림차순으로 정렬된 수열에서 부분 수열의 합이 k가 되는 가장 짧은 구간의 시작 인덱스와 마지막 인덱스를 구해주는 문제다.

해설

처음 접근을 완전 탐색으로 했더니 시간 초과가 발생하여, 투포인터 알고리즘을 이용해 풀었다.

해당 문제는 아래와 같이 접근하면 된다.

 

1. left와 right 인덱스를 지정해주고 left부터 right 전까지의 부분 수열의 합을 sum이라 가정하자

2. 구해야하는 합 k보다 작다면 right를 오른쪽으로 이동해서 sum의 크기를 키워주고

3. 구해야하는 k보다 크다면 left를 오른쪽으로 이동해서 sum의 크기를 줄여주고

4. sum이 k와 같다면 left부터 right까지의 길이가 기존에 구한 left부터 right의 길이보다 짧다면 새롭게 갱신해 주면 되는 문제다.

 

그림으로 이해하면 좋을 것 같아서 준비했다.

[1, 1, 1, 2, 3, 4, 5] 부분 수열과 k가 5인 짧은 부분 수열을 구하는 예시이다.

 

 

예시1

 

left부터 right 전까지 더해줘서 sum은 1이 나오며, k 보다 작으므로 right를 이동시켜줘야한다.

 

예시2

 

right를 옮겼지만 여전히 sum이 작아서 right를 이동해야 한다.

 

예시3와 예시4

 

1. 위와 같이 right를 이동하다 sum이 k와 같아지는 구간을 발견했다

2. 기존에 left와 right를 기록된 게 없으니 left는 0 right는 3으로 세팅해준다.

3. 또한 sum과 k가 같은 구간은 left와 right를 한 칸씩 이동해 준다.(나는 left만 이동시켰다. right를 이동시키면 코드가 조금 더 복잡해져서 성능보단 가독성을 선택했다.)

 

예시5

 

1. left를 이동하면서 0번 인덱스의 value는 sum에서 빼줬다.

2. 이젠 sum이 k보다 작으니 right를 오른쪽으로 이동시켜 준다.

 

예시6

 

right를 이동시켜 줬더니 sum이 k보다 커졌다. left를 오른쪽으로 이동시켜 값을 줄여주자.

 

예시7과 예시8

 

1. left를 이동시키면서 sum을 줄여주다 보니 sum과 k가 같아지는 구간을 만났다.

2. 기존에 left와 right의 길이보다 짧은 구간이므로 left와 right의 값을 3, 4로 변경해준다.

3. sum과 k가 같은 구간이므로 left만 이동시켜 준다.(right도 같이 이동해 줘도 된다.)

 

예시9와 예시10

 

반복해 준다.

 

예시11과 예시12

 

여기서 중요한 건 right가 배열의 마지막 인덱스보다 커지더라도 멈추면 안 된다. left가 줄어들면서 sum과 k가 같아지는 구간이 있을 수 있기 때문이다.

 

예시13

 

1. sum과 k가 같아지는 구간이 발견되어 기존 left와 right 길이와 비교하여 세팅해 준다.

2. 위와 같이 left까지 다 탐색이 끝나면 종료해 준다.

 

코드

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[]{0, sequence.length - 1};
    
        int left = 0;
        int right = 1;
        
        int sum = sequence[0];
        
        while(left < right) {
            if (sum == k) {
                change(right, left, answer);
                sum -= sequence[left++];
                
            } else if (sum > k) {
                sum -= sequence[left++];
            } else if (right < sequence.length) {
                sum += sequence[right++];
            } else {
                break;
            }
        }
        
        return answer;
    }
  
    private void change(int right, int left, int[] answer) {
        if (right - 1 - left < answer[1] - answer[0]) {
                answer[0] = left;
                answer[1] = right - 1;
        }
    }
}