프로그래머스 | Level 2 | 연속된 부분 수열의 합

Sep 03, 2024

Published byJynn

999

Programmers | Level 2 | 연속된 부분 수열의 합

Problems

📘 Src: Programmers
🗂️ Cat: Two Pointers

󰧭 Description

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

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

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

 Constraints

5 ≤ sequence의 길이 ≤ 1,000,000
1 ≤ sequence의 원소 ≤ 1,000
sequence는 비내림차순으로 정렬되어 있습니다.
5 ≤ k ≤ 1,000,000,000
k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.

󰦕 Examples

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]`

Solutions

󰘦 Code

Solution.java

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int left = 0;  // 부분 수열의 시작 인덱스
        int right = 0;  // 부분 수열의 끝 인덱스
        int sum = sequence[0];  // 현재 부분 수열의 합
        int max = sequence.length;  // 수열의 최대 길이
        int[] result = new int[]{0, Integer.MAX_VALUE};  // 결과를 저장할 배열, 초기값은 최대값으로 설정
        
        // 투 포인터를 이용한 부분 수열 탐색
        while (right < max) {
            if (sum < k) {  // 현재 합이 k보다 작은 경우
                right++;  // right 포인터를 오른쪽으로 이동
                if (right < max) sum += sequence[right];  // 새로운 요소를 부분 수열에 포함
                continue;
            }
            
            if (sum == k) {  // 현재 합이 k와 같은 경우
                if (right - left < result[1] - result[0]) {  // 부분 수열이 더 짧은 경우
                    result[0] = left;  // 시작 인덱스를 갱신
                    result[1] = right;  // 끝 인덱스를 갱신
                }
                sum -= sequence[left];  // left 포인터를 오른쪽으로 이동하여 현재 합에서 제외
                left++;
                continue;
            }
            
            if (sum > k) {  // 현재 합이 k보다 큰 경우
                sum -= sequence[left];  // left 포인터를 오른쪽으로 이동하여 현재 합에서 제외
                left++;
                continue;
            }
        }
        
        return result;  // 가장 짧은 부분 수열의 시작과 끝 인덱스를 반환
    }
}

 Approach

이 문제는 정렬된 수열에서 주어진 합 k를 만족하는 가장 짧은 연속된 부분 수열을 찾는 문제입니다. 이를 해결하기 위해 투 포인터(Two Pointers) 기법을 사용하여 효율적으로 부분 수열을 탐색합니다.

1. 문제 분석

이 문제는 정렬된 수열에서 특정 합을 가지는 가장 짧은 부분 수열을 찾는 문제로, 다음과 같은 요소를 고려해야 합니다:

정렬된 수열: 수열이 비내림차순으로 정렬되어 있으므로, 두 포인터를 사용하여 특정 범위의 합을 계산하고, 필요한 경우 포인터를 이동시켜야 합니다.
최적의 부분 수열 찾기: 여러 부분 수열이 동일한 합을 가질 수 있으므로, 그중 가장 짧고, 시작 인덱스가 가장 작은 수열을 찾아야 합니다.
투 포인터 기법: 연속된 부분 수열의 합을 계산하기 위해 두 개의 포인터를 사용하여 수열의 구간을 확장하거나 축소하는 방식으로 문제를 해결할 수 있습니다.

2. 접근 방식

이 문제를 해결하기 위해 투 포인터 기법을 사용하여 연속된 부분 수열을 탐색합니다. 이를 통해, 수열을 효율적으로 탐색하고, 합이 k인 가장 짧은 부분 수열을 찾아냅니다.

포인터 초기화: left와 right 포인터를 초기화하여 수열의 시작 부분을 가리키도록 설정합니다.
부분 수열 합 계산: 두 포인터 사이의 부분 수열의 합을 계산하고, 이 합이 k보다 작으면 right 포인터를 이동시키고, 합이 k보다 크면 left 포인터를 이동시킵니다.
최적의 수열 갱신: 합이 정확히 k일 때, 현재 부분 수열의 길이가 이전에 찾은 수열보다 짧다면 결과를 갱신합니다.
탐색 종료: 두 포인터 중 하나가 수열의 끝에 도달하면 탐색을 종료합니다.

3. 초기 포인터 설정 및 합 계산

먼저, 부분 수열의 시작과 끝을 나타내는 포인터를 초기화하고, 초기 합을 계산합니다. 이때 두 포인터는 수열의 첫 번째 원소를 가리키며, 합은 배열의 첫 번째 원소로 설정됩니다. 또한, 결과를 저장할 배열은 부분 수열의 시작과 끝 인덱스를 저장하며, 초기값을 최대값으로 설정해 더 짧은 부분 수열이 발견될 때마다 갱신합니다.

Solution.java

int left = 0;  // 부분 수열의 시작 인덱스
int right = 0;  // 부분 수열의 끝 인덱스
int sum = sequence[0];  // 초기 합은 첫 번째 원소로 시작
int max = sequence.length;  // 수열의 길이
int[] result = new int[]{0, Integer.MAX_VALUE};  // 결과를 저장할 배열 초기화

4. 투 포인터를 사용한 부분 수열 탐색

이제, 두 포인터를 사용해 주어진 수열에서 조건을 만족하는 부분 수열을 찾아내고, 가장 작은 인덱스를 가진 부분 수열을 찾는 과정을 반복합니다. 이 과정에서는 세 가지 주요 경우의 수가 발생하며, 각 경우에 따라 포인터의 이동과 합의 조정이 이루어집니다.

부분 수열의 합이 k보다 작은 경우: 현재 부분 수열의 합이 목표 값 k에 도달하지 못한 상황입니다. 이 경우, right 포인터를 오른쪽으로 이동시켜 부분 수열에 새로운 요소를 포함시킴으로써 합을 증가시킵니다.
부분 수열의 합이 k와 같은 경우: 현재 부분 수열의 합이 정확히 k와 일치합니다. 이때, 현재 부분 수열의 길이가 이전에 기록된 부분 수열보다 짧다면, 결과를 갱신합니다. 이후, left 포인터를 오른쪽으로 이동시켜 더 짧은 부분 수열을 찾을 가능성을 탐색합니다.
부분 수열의 합이 k보다 큰 경우: 현재 부분 수열의 합이 k를 초과한 상황입니다. 이는 부분 수열이 너무 길거나 포함된 숫자가 커서 목표 값을 넘어선 것을 의미합니다. 이 경우, left 포인터를 이동시켜 부분 수열의 길이를 줄이고, 합을 감소시킴으로써 다시 k에 맞추도록 조정합니다.

이러한 세 가지 경우에 따라 right 포인터와 left 포인터를 적절히 이동시키며, 최종적으로 목표 값을 만족하는 가장 짧은 부분 수열을 찾아냅니다.

Solution.java

while (right < max) {
    if (sum < k) {  // 현재 합이 k보다 작은 경우
        right++;  // right 포인터를 오른쪽으로 이동
        if (right < max) sum += sequence[right];  // 새로운 요소를 합에 추가
        continue;
    }
    
    if (sum == k) {  // 현재 합이 k와 같은 경우
        // 더 짧은 부분 수열을 발견하면 결과를 갱신
        if (right - left < result[1] - result[0]) {
            result[0] = left;  // 시작 인덱스 갱신
            result[1] = right;  // 끝 인덱스 갱신
        }
        sum -= sequence[left];  // left 포인터가 가리키는 값을 합에서 제외
        left++;  // left 포인터를 오른쪽으로 이동
        continue;
    }
    
    if (sum > k) {  // 현재 합이 k보다 큰 경우
        sum -= sequence[left];  // left 포인터가 가리키는 값을 합에서 제외
        left++;  // left 포인터를 오른쪽으로 이동
        continue;
    }
}

5. 최종 결과 반환

모든 탐색이 끝나면, result 배열에 조건을 만족하는 가장 짧은 부분 수열의 시작 인덱스와 끝 인덱스가 담겨 있습니다. 이 배열을 반환하여 최종 결과를 제공합니다.

Solution.java

// 가장 짧은 부분 수열의 시작과 끝 인덱스 반환
return result;

󰄉 Complexity

⏳ TC: O(n)
💾 SC: O(1)

이 알고리즘은 sequence 배열을 한 번 순회하면서 두 포인터를 사용해 부분 수열을 탐색하므로, 시간 복잡도는 O(n)입니다. 추가적인 메모리를 사용하지 않으므로, 공간 복잡도는 O(1)입니다. 이 알고리즘은 효율적인 탐색 기법을 사용하여 주어진 조건을 만족하는 최적의 결과를 도출합니다.

Algorithm
Two Pointers