[프로그래머스] 연속된 부분 수열의 합 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제는 합을 만족시키는 부분 수열을 모두 구하고 부분 수열 중 가장 길이가 짧은 부분 수열, 길이가 동일하다면 가장 앞쪽 부분 수열을 찾는 문제이다.

배열에서 원소를 하나씩 추가시키며 합을 확인한다.

합이 아직 작을 경우 뒤 원소를 하나 추가시키고 클 경우 앞 원소를 하나 줄이며 부분 수열을 지정한다.

만약 합이 일치할 경우 해당 부분 수열의 시작 인덱스와 끝 인덱스를 저장하고 앞 원소를 하나 줄인다.

가장 길이가 짧은 부분 수열을 찾아야 하므로 두 인덱스 사이의 차가 작은 순서대로 정렬하면 제일 앞부분 수열이 가장 길이가 짧고 가장 앞쪽 부분 수열이 된다.

 

1. 부분 수열의 시작과 끝 인덱스를 저장할 리스트를 생성한다. li = list()
2. 부분 수열의 시작 인덱스를 저장할 변수를 생성하고 초기화한다. start = 0
3. 부분 수열의 끝 인덱스를 저장할 변수를 생성하고 초기화한다. end = 0
4. 부분 수열의 합을 저장할 변수를 생성하고 처음 부분 수열의 시작 값을 저장한다. result = sequence[end]
5. 시작 인덱스와 끝 인덱스가 모두 정수 배열의 원소를 가리킬 수 있으면 반복한다. while (start < len(sequence)) and (end < len(sequence))
6. 만약 부분 수열의 합이 아직 작을 경우 if (result < k)
7. 끝 인덱스를 증가시켜 end += 1
8. 만약 증가시킨 끝 인덱스에 해당하는 원소가 있으면 if (end < len(sequence))
9. 부분 수열에 원소를 하나 추가한다. result += sequence[end]
10. 반면에 부분 수열의 합이 일치하거나 클 경우 else
11. 만약 일치한다면 if (result == k)
12. 부분 수열의 시작 인덱스와 끝 인덱스를 리스트로 추가한다. li.append([start, end])
13. 부분 수열에 원소를 하나 제거하고 result -= sequence[start]
14. 시작 인덱스를 증가시킨다. start += 1
15. 모든 가능한 부분 수열을 찾았다면 길이가 가장 짧은 부분 수열을 찾아야 하므로 시작 인덱스와 끝 인덱스의 차이가 작은 순서대로 정렬한다. li.sort(key = lambda x : x[1] - x[0])
16. 길이가 가장 짧은 부분 수열의 시작 인덱스와 끝 인덱스를 저장한다. answer = li[0]

반응형

3. 소스코드

def solution(sequence, k):
    answer = []
    
    li = list()
    
    start = 0
    end = 0
    result = sequence[end]
    while (start < len(sequence)) and (end < len(sequence)):
        if (result < k):
            end += 1
            if (end < len(sequence)):
                result += sequence[end]
            
        else:
            if (result == k):
                li.append([start, end])

            result -= sequence[start]
            start += 1
        
    li.sort(key = lambda x : x[1] - x[0])
    answer = li[0]
    
    return answer