본문 바로가기
백준 & 프로그래머스

프로그래머스.연속된 부분 수열의 합.py

by concho 2023. 9. 7.

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

ex) 

sequence =[1, 1, 1, 2, 3, 4, 5]
k = 5

1) 합이 k보다 작을 때 마다 end를 밀고 그 값을 더해준다.

1 1 1 2 3 4 5
  start - end            
1            
1 1 1 2 3 4 5
  start end          
  2          
1 1 1 2 3 4 5
  start   end        
    3        

2) 합이 k와 같다면 {key = 인덱스 간의 차, value = start, end} 를 answer에 저장해 주고

1 1 1 2 3 4 5
  start     end      
      5      

3) start의 값을 뺀 후 start를 민다.

1 1 1 2 3 4 5
    start   end      
      4      

4) k보다 작아졌으니까 end한번 밀고, 더해주고

1 1 1 2 3 4 5
    start     end    
        7    

5) 위에서 합은 k보다 크니까 start에 있는 값을 빼고 start를 밀어준다

1 1 1 2 3 4 5
      start   end    
        6    

 

1 1 1 2 3 4 5
        start end    
        5    

6) 또 k니까 같은 방식으로 저장해주고, 빼주고, start를 민다.

1 1 1 2 3 4 5
          start - end    
        3    

7) 반복...

정확성 테스트
테스트 1 통과 (0.01ms, 10.3MB)
테스트 2 통과 (0.01ms, 10.2MB)
테스트 3 통과 (0.07ms, 10.3MB)
테스트 4 통과 (0.66ms, 10.2MB)
테스트 5 통과 (8.49ms, 10.5MB)
테스트 6 통과 (5.41ms, 10.7MB)
테스트 7 통과 (18.17ms, 11.7MB)
테스트 8 통과 (52.10ms, 13.3MB)
테스트 9 통과 (82.11ms, 16.4MB)
테스트 10 통과 (239.89ms, 26.5MB)
테스트 11 통과 (387.88ms, 42.9MB)
테스트 12 통과 (347.55ms, 43MB)
테스트 13 통과 (395.90ms, 43.1MB)
테스트 14 통과 (442.27ms, 43.2MB)
테스트 15 통과 (495.12ms, 43.1MB)
테스트 16 통과 (235.36ms, 51.3MB)
테스트 17 통과 (622.50ms, 51.2MB)
테스트 18 통과 (0.02ms, 10.3MB)
테스트 19 통과 (0.01ms, 10.2MB)
테스트 20 통과 (0.01ms, 10.1MB)
테스트 21 통과 (0.01ms, 10.1MB)
테스트 22 통과 (0.01ms, 10.1MB)
테스트 23 통과 (0.01ms, 10.2MB)
테스트 24 통과 (495.88ms, 18.6MB)
테스트 25 통과 (215.24ms, 18.7MB)
테스트 26 통과 (434.44ms, 18.6MB)
테스트 27 통과 (368.73ms, 18.5MB)
테스트 28 통과 (327.62ms, 18.5MB)
테스트 29 통과 (300.20ms, 18.5MB)
테스트 30 통과 (429.33ms, 51.3MB)
테스트 31 통과 (0.01ms, 10.3MB)
테스트 32 통과 (0.01ms, 10.1MB)
테스트 33 통과 (0.01ms, 10.2MB)
테스트 34 통과 (0.01ms, 10.2MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0

 

 

def solution(sequence, k):
    answer_dic = dict()
    sum_result, start_index,end_index,answer_flag = sequence[0],0,0,False
    while start_index < len(sequence):
        if sum_result < k:
            end_index += 1
            if end_index >= len(sequence): break
            sum_result += sequence[end_index]
        elif sum_result > k or answer_flag == True:
            answer_flag = False
            sum_result -= sequence[start_index]
            start_index += 1
        else:
            if not end_index - start_index in answer_dic:
                answer_dic[end_index - start_index] = [start_index, end_index]
            answer_flag = True
    return answer_dic[min(answer_dic)]

댓글