[프로그래머스] 연속된 부분 수열의 합 Java, c++, python

문제 설명

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

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 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]

풀이

java

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[] {-1, -1};
        
        int sum = 0, start = 0, end = 0;
        for(int i = 0; i < sequence.length; i++){
            end = i;
            sum += sequence[i];
            while(k < sum){
                sum -= sequence[start++];
            }
            if(k == sum){
                if((answer[0] == -1 && answer[1] == -1) || end - start < answer[1] - answer[0]){
                    answer[0] = start;
                    answer[1] = end;
                }
            }
        }
        
        return answer;
    }
}

java는 c++과 다르게 포인터에 직접 접근하여 사용하지 않는 언어입니다.

객체 선언 new를 사용하여 동적 메모리 할당 영역에 메모리를 잡는 방식을 사용합니다.

answer는 primitive type(기본 타입)으로 int 형입니다. 초기화 후에는 데이터 추가 및 삭제가 불가하니 사용에 유의해야합니다. 컨테이너 메소드를 사용하고 싶다면 참조 타입으로 사용해야합니다.

reference type(참조 타입) 중 ArrayList로 배열을 사용한다면 int형은 사용하지 못하고 Integer형을 사용해야 합니다. 

 

c++

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    
    vector<int> answer(2, 0);
    queue<pair<int, int>> q;
    int n = sequence.size(), len = 1000001, sum = 0;
    
    for(int i = 0; i < n; i++){
        q.push({sequence[i], i});
        sum += sequence[i];
        while(sum > k){
            sum -= q.front().first;
            q.pop();
        }
        if(sum == k && q.size() < len){
            len = q.size();
            answer[0] = q.front().second;
            answer[1] = q.back().second;
        }
    }
    
    return answer;
}

 

다른 풀이

#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {

   vector<int> answer;
   int start = 0, end = 0, sum = 0;
   for(int i = 0; i < sequence.size(); i++){
        end = i;
        sum += sequence[end];
        while(sum > k){
            sum -= sequence[start++];
        }
        if(sum == k){
            if(answer.empty() || end - start < answer[1] - answer[0]){
                answer = {start, end};
            }
        }
   }
    
    return answer;
}

 

python

def solution(sequence, k):
    answer = []
    
    sum = 0
    start = 0
    end = 0
    for i in range(len(sequence)):
        end = i
        sum += sequence[end]
        while k < sum:
            sum -= sequence[start]
            start += 1
        if k == sum:    
            if len(answer) == 0 or end - start < answer[1] - answer[0]:
                answer = [start, end]
        
    return answer