프로그래머스 | 연속된 부분 수열의 합 | python 풀이

문제

https://school.programmers.co.kr/learn/courses/30/lessons/178870#qna

프로그래머스

문제 설명

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

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

내 답안

def solution(sequence, k):
    answer = []
    start, end = 0,0
    temp = sequence[0]
    min_len = 1000001

    while start <= end < len(sequence):
        if temp == k :
            if end - start + 1 < min_len :
                min_len = end - start + 1
                answer = [start, end]
            temp -= sequence[start]
            start += 1

        elif temp < k :
            end += 1
            if end < len(sequence) :
                temp += sequence[end]

        elif temp > k :
            temp -= sequence[start]
            start += 1

    return answer

해설

부분 수열의 시작과 끝을 나타내는 포인터 start, end 를 활용하였다.

내가 생각했을 때 이 문제에서 중요한 부분은, 찾아야 하는 부분수열의 길이는 최대한 짧아야 한다는 것이다. 이걸 염두에 두지 않고 문제를 풀면 풀이가 이상한 방향으로 흘러가기 쉽다.

길이를 최소화하면서 k와 가까운 합계 temp를 만들어내야 하므로,

• 현재 부분수열의 합(temp)가 k보다 크다? : temp에서 가장 작은 값 제거 => 시작 인덱스의 값(sequence[start]) 제거 후 시작 인덱스 1 증가
• 현재 부분수열의 합(temp)가 k보다 작다? : 추가할 수 있는 값 중 가장 큰 값을 추가 => 끝 인덱스 1 증가 후 temp에 추가

temp와 k가 일치하면

• 최소 길이를 가진 경우에만 answer 값에 start, end 저장
• 더 짧은 길이를 가진 수열이 있을 수 있으므로, start 값 한 칸 이동

피드백

한 30분 정도 고민하다가 도저히 답이 안나와서 구글링으로 다른사람들의 풀이를 참조했다.

 

풀이가 되게 다양하고 정형화된 풀이법도 없어서 그런가 솔직히 이해하기 어려운 코드들도 많았는데 그나마 쉬운 풀이법을 찾을 수 있었다. 물론 아직까지 왜 되지? 싶은 것들이 있다.

 

특히나 temp < k 일 때, end 포인터를 한 칸 뒤로 옮겨주는데 이때의 end 값이 sequence의 길이보다 작을 때만 temp값을 갱신한다. 그런데 end 값이 sequence의 길이를 넘기면 즉, 인덱스를 초과하면 취하는 특정 액션이 없다. 그냥 end+1을 한 상태로 while 문을 빠져나오고 탐색이 종료된다. 나는 여기서 분명 예외가 발생할거라 예상하고 제출했었다. 그런데도 무사히 통과되길래 굉장히 당황스러웠다.

 

뿐만아니라 코드의 동작원리에 대해서도 완벽하게 이해하지 못했다. 나중에 꼭 다시 풀어봐야 할 것 같다.

 

체감상 백준보다 프로그래머스 문제가 더 까다로운 것 같다..후