[프로그래머스] 연속된 부분 수열의 합 - 자바(Java)

문제 링크

프로그래머스

 

문제 설명

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 k 입니다.
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
• 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

수열을 나타내는 정수배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

제한사항

• 5 ≤ sequence의 길이 ≤ 1,000,000 
  • 1 ≤ sequence의 원소 ≤ 1,000 
  • sequence는 비내림차순으로 정렬되어 있습니다. 
• 5 ≤ k ≤ 1,000,000,000 
  • k는 항상 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]

 

문제 풀이

 

[고려사항]

sequence는 최대 1,000,000(100만)개이니까 시간 복잡도를 고려해서 구현해야한다.

O(N^2)이 되면 1,000,000,000,000가 되어서 시간 초과로 실패할 것이기 때문이다.

 

[처음 생각으로만 한 풀이방법]

아래와 같이 풀면 배열의 길이가 n인 경우, 누적합의 조합 수는 (n-1)+(n-2)+(n-3)+...+1이므로, n*(n-1)-상수여서 O(N^2)이 되니까 안된다.

우선순위는 1) 인덱스가 작은 값 2) 짧은 길이니까 오름차순으로 정렬된 배열 순회시에는 인덱스 0부터 누적합이 k가 될때 까지 순회한다.

누적합이 k와 같아지면 시작 인덱스와 마지막 인덱스를 저장한다.

조건에 맞는 인덱스를 찾아야하므로 다음 인덱스에서 다시 누적합을 구한다.

누적하다가 특정 인덱스 값을 누적했을때 k 를 초과하면 순회를 마치고 다시 반복한다.

누적합이 되는 경우, 저장한 인덱스의 길이가 가장 짧은 것으로 갱신한다.

(1,2)와 (3,5)가 누적합이 된 경우라면 2-1 < 5-3이므로 (1,2)를 정답 인덱스로 저장한다.

길이가 같은게 있다면, 시작 인덱스가 더 작은 값을 정답 인덱스로 저장한다.

 

[실제 구현한 알고리즘 / 구현방법]

이 문제는 특정 조건을 만족하는 부분 구간을 구하는 문제이므로 투 포인터(Two Pointer) 알고리즘을 이용해서 풀면 된다.

투 포인터(Two Pointer) 알고리즘은 일반적으로 배열이 정렬되어 있을 때 사용하는 알고리즘이다.

투 포인터 알고리즘은 선형시간 복잡도를 가지므로 효율적이고, 한 번의 반복으로 모든 요소를 처리할 수 있다.

 

배열을 순회하면서 누적합을 앞에서부터 구하면 되니까

start pointer를 0번에 두고 end pointer의 인덱스를 이동시키면서 누적 합을 구한다.

누적 합이 k 를 초과하면 start pointer를 이동시켜서 start ~ end pointer의 합을 구한다.

이때 마지막으로 저장된 누적 합에서 sequence[start pointer]를 빼주면 현재의 start ~ end pointer의 합이 된다.

예를 들어, [1,2,3,4,5]라면 1부터 4까지 누적하면 합이 10이므로 k를 넘어선다.

이때 start pointer를 2로 옮기면 2부터 4까지의 합인데, 이 합은 10에서 1을 뺀 9이다.

 

그렇게 진행하다가 누적합이 k와 같아지면 해당 start pointer와 end pointer를 반환한다.

start, end pointer를 앞쪽 인덱스부터 시작하면 가장 짧은 길이 + 가장 작은 인덱스 값을 만족시키는 인덱스를 반환할 수 있다.

 

[풀이 과정]

1. 첫번째 인덱스부터 start pointer와 end pointer가 마지막 인덱스를 가리킬때까지, 아래 과정을 반복하여 정답 후보를 구한다.
   1. 누적 합이 k인 경우(sum==k), 정답 후보에 해당 인덱스를 저장한다.(start pointer, end pointer)
   2. 누적 합이 k보다 작고(sum<k), end pointer가 마지막 인덱스가 아니라면, end pointer를 한 칸 이동하고, 누적 합을 계산한다.
   3. 누적 합이 k보다 크거나(sum>k), end pointer가 마지막 인덱스라면, 현재 start pointer의 값을 누적 합에서 빼주고 start pointer를 한 칸 이동한다. 
2. 정답 후보 중 1) 길이가 짧고, 2) 인덱스가 가장 작은 부분 수열 인덱스를 반환한다.

[구현시 고려한 사항]

최종 답을 list에서 SubSequence 클래스의 left, right를 각각 가져와서 int배열로 반환을 할지 고민했는데, 

• 즉, return new int[]{answerList.get(0).left, answerList.get(0).right};

SubSequence 클래스에 (left, right)를 int 배열로 반환하는 함수(getSequence)를 생성해서 반환하는 걸로 구현했다.

함수를 생성하는게 가독성이 좋고, 

• return answerList.get(0).getSequence();

생성한 SubSequence 클래스의 요소를 조합해서 반환하는 것이므로 SubSequence 클래스에 함수를 생성하는 것이 이 클래스의 목적성도 좀 더 명확하다고 생각했기 때문이다.

 

코드

public class Solution {
    public static int[] solution(int[] sequence, int k) {
        int startPointer = 0;
        int endPointer = 0;
        List<SubSequence> answerList = new ArrayList<>(); // 정답 후보 저장할 리스트

        int sum = sequence[startPointer];
        int length = sequence.length;
        while (true) { // end pointer가 마지막 인덱스를 탐색할 때까지
            if (sum == k) answerList.add(new SubSequence(startPointer, endPointer, endPointer-startPointer+1));

            if (startPointer == length - 1 && endPointer == length - 1) break;

            if (sum < k && endPointer < length - 1) { // 누적 합이 k보다 작다면
                endPointer++; // end pointer 한칸 이동
                sum += sequence[endPointer]; // 누적 합 계산
            } else { // 누적 합이 k보다 크거나 end pointer가 마지막 인덱스라면
                sum -= sequence[startPointer]; // 움직인 start pointer에서 end pointer까지의 누적합은 움직이기 전 start pointer를 뺀 값
                startPointer++; // start pointer 이동
            }
        }
        // 정답 후보에서 1) 길이가 짧고 2) 인덱스가 작은 부분 수열 인덱스를 반환
        answerList.sort(SubSequence::compareTo);

        return answerList.get(0).getSequence();
    }

    public static class SubSequence implements Comparable<SubSequence> {
        int left, right, size;
        public SubSequence(int left, int right, int size) {
            this.left = left;
            this.right = right;
            this.size = size;
        }

        public int[] getSequence() {
            return new int[]{this.left, this.right};
        }

        @Override
        public int compareTo(SubSequence o) {
            if (this.size == o.size) return this.left - o.left;
            else return this.size - o.size;
    }
}