[프로그래머스] 연속된 부분 수열의 합(파이썬)

🗓️ 문제 설명

• 비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.
  • 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
  • 부분 수열의 합은 k입니다.
  • 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
  • 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.
• 수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 반환하세요.(수열의 인덱스는 0부터 시작합니다.)
• 제한 사항
  • 5 ≤ sequence의 길이 ≤ 1000000
    • 1 ≤ sequence의 원소 ≤ 1000
    • sequence는 비내림차순으로 정렬
  • 5 ≤ k ≤ 1000000000
    • 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]

 

💻 코드

최종 코드

• 수정사항
  >> n과 idx, length를 반복문 외부로 꺼내 중복 계산을 방지했습니다.
  >> sequence에서 값을 꺼내 뺄셈하는 방식에서 덧셈하는 방식으로 변경했습니다.

 

코드 풀이

 

다른 사람 풀이

풀이 1번

1. 4번줄 : 시작 인덱스와, 끝 인덱스를 변수에 저장
2. 5번줄 : sequence의 첫 값을 acc에 저장
3. 7번줄 : 임의의 큰 값을 min_len에 저장
4. 8번줄 : 시작 인덱스가 끝 인덱스와 같거나 작고, 끝 인덱스가 sequence의 길이보다 작으면 계속되는 반복문 실행
5. 9~12번줄 : 시작 인덱스가 끝 인덱스보다 크다면 acc에 sequence의 시작 인덱스 값을 더하고, 끝 인덱스에 시작 인덱스를 저장
6. 14번줄 : acc와 k가 같은지 확인하는 조건문 실행
7. 15~16번줄 : min_len 값이 시작 인덱스와 끝 인덱스의 길이보다 길다면 min_len을 시작 인덱스와 끝 인덱스의 길이로 저장 
8. 17번줄 : answer에 시작 인덱스와 끝 인덱스를 저장
9. 18~19번줄 : acc에서 sequence의 시작 인덱스 값을 빼고, 시작 인덱스에 1을 더함
10. 20~22번줄 : acc가 k보다 크다면 acc에서 sequence의 시작 인덱스 값을 빼고, 시작 인덱스에 1을 더함
11. 23~26번줄 : acc가 k보다 작다면 끝 인덱스에 1을 더하고, 끝 인덱스가 sequence의 길이보다 작다면 acc에서 sequence의 마지막 인덱스 값을 더해줌
12. 28번줄 : answer를 반환

 

⚙️ 시행착오

1차 시도

• 테스트 실패 : 17개의 테스트에서 시간초과 발생