[프로그래머스] 연속된 부분 수열의 합

 

🔗문제 링크

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

프로그래머스

 

 

❓접근 방법

• 투 포인터 (Two Pointer)
  • 리스트에서 2개의 포인터를 가지고 왔다갔다 하는 방법.
  • 보통 정렬이 된 상황에서 쓰임.
  • 파이썬에서 정렬의 시간 복잡도는 보통 O(nlogn)이므로, 이중 for문을 사용하는 O(n^2)보다 효율성이 좋다.
  • example : two sum
    
    • list : 1 3 4 5 7 9 16 
    • target : 14
    • 정렬한 후 양 끝에서 포인터를 시작해 두 포인터를 더한 값이 target보다 크면 오른쪽 포인터를 왼쪽으로, target보다 작으면 왼쪽 포인터를 오른쪽으로!
      • 1 + 16 = 17 >14
      • 1 + 9 = 10 < 14
      • 3 + 9 = 12 < 14
      • 4 + 9 = 13 < 14
      • 5 + 9 = 14 👈 찾았다!

📝A4용지 풀이

 

 

🧑‍💻코드

def solution(sequence, k):
    answer = []
    answer_list = []
    start, end = 0, 0
    len_seq = len(sequence)
    
    sum = sequence[0]
    
    while (start <= end) and (start != len_seq):
        
        if sum > k: 
            sum -= sequence[start]
            start += 1
            
        elif sum < k:
            if end == len_seq - 1:
                sum -= sequence[start]
                start += 1
            else:
                end += 1
                sum += sequence[end]
                
        elif sum == k:
            answer_list.append([end-start, [start, end]])
            sum -= sequence[start]
            start += 1
    
    answer_list.sort()
    answer = answer_list[0][1]

    return answer

 

최적화가 더 필요할 듯 싶지만... 일단 투포인터 유형을 익히는 것이 목표이므로 투포인터를 구현에 사용했다는 점에 의의를 두었다.

이중 리스트와 .sort()를 활용하는 방법은 매번 lambda 사용법을 까먹는(...) 나에게는 기억해두면 아주 좋은 방법 같다.