프로그래머스, 연속된 부분 수열의 합(python, java)

문제 설명

수열과 목표 값 k가 주어질 때 연속된 부분 수열의 합 중 길이가 가장 짧은 경우를 구하는 문제이다. 만일 길이가 가장 짧은 게 여러 개 있다면 시작 인덱스가 제일 작은 부분 수열을 반환한다.

https://school.programmers.co.kr/learn/courses/30/lessons/178870?language=java 

프로그래머스

문제 풀이

첫 번째 접근

투 포인터로 문제를 풀어줬다. 그리고 제일 범위가 작은 것이 우선 순위에 들어가 있기 때문에 뒤에서부터 탐색했다.

 

반복문

1. sum과 k가 같은 경우, tmp에 해당 인덱스들의 위치와 차이를 넣어 준 다음에 sum과 end를 조정한다. 바로 break하지 않는 이유는 길이가 짧은 부분 수열이 여러 개 있으면 제일  앞에서 시작하는 것이 답이기 때문이다.

2. sum이 k보다 작으면 start를 뒤로 밀어서 범위를 넓힌 다음에 sum에 해당하는 값을 더해줬다.

3. sum이 k보다 크면 sum에 end 인덱스가 위치한 값을 빼주고 end의 값을 하나 줄여서 범위를 좁혀줬다.

 

탈출

1. start과 end가 모두 0인 경우에는 sum이 k와 같으면 tmp에 값을 넣어준 다음에 탈출.

2. start이 0이라면 end만 조정해줘야 한다. 그러므로 sum이 k와 값을 넣어준 다음에 탈출. 어차피 범위를 좁힐 것이기 때문에 sum과 k가 같은 경우는 나타나지 않기 때문이다. 그렇지 않다면 end에 1을 계속 빼서 값을 조정해야 한다.

 

정렬

1. 범위를 기준으로, 만일 범위가 같으면 시작 인덱스를 기준으로 정렬했다.

 

정답

1. 맨 앞에 있는 값의 start와 end를 넣어줬다.

코드

python

def solution(sequence, k):
    answer = []
    length = len(sequence)
    start = length-1
    end = length-1
    sum = sequence[length-1]
    tmp = []
    
    while True:
        
        if start == 0 and end == 0:
            if sum == k:
                tmp.append([start, end, (end-start)])
            break
        
        if start == 0:
            if sum == k:
                tmp.append([start, end, (end-start)])
                break
            sum -= sequence[end]
            end -= 1
            continue
        
        if sum == k:
            tmp.append([start, end, (end-start)])
            sum -= sequence[end]
            end -= 1
        elif sum < k:
            start -= 1
            sum += sequence[start]
        elif sum > k:
            sum -= sequence[end]
            end -= 1
    
    tmp.sort(key=lambda x : (x[2], x[0]))
    # print(tmp)
    
    answer.append(tmp[0][0])
    answer.append(tmp[0][1])
    return answer

java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Collections;

class Solution {
    static class Index{
        int start;
        int end;
        int range;

        public Index(int start, int end, int range){
            this.start = start;
            this.end = end;
            this.range = range;
        }

    }
    
    public int[] solution(int[] sequence, int k) {
        List<Index> tmp = new ArrayList<>();
        int length = sequence.length;
        int start = length-1;
        int end = length-1;
        int sum = sequence[length-1];
        int[] answer = new int[2];
        
        while(true){
            if(start == 0 && end == 0){
                if(sum == k){
                    tmp.add(new Index(start, end, (end-start)));
                }
                break;
            }
            if(start == 0){
                if(sum == k){
                    tmp.add(new Index(start, end, (end-start)));
                    break;
                }
                sum -= sequence[end];
                end -= 1;
                continue;
            }

            if(sum == k){
                tmp.add(new Index(start, end, (end-start)));
                sum -= sequence[end];
                end -= 1;
            }else if(sum < k){
                start -= 1;
                sum += sequence[start];
            }else if(sum > k){
                sum -= sequence[end];
                end -= 1;
            }
        }
        
        Collections.sort(tmp, new Comparator<Index>() {
            @Override
            public int compare(Index o1, Index o2) {
                if(o1.range == o2.range){
                    return o1.start - o2.start;
                }
                return o1.range - o2.range;
            }
        });
        
        answer[0] = tmp.get(0).start;
        answer[1] = tmp.get(0).end;

        return answer;
    }
}