[99클럽 코테 스터디 23일차 TIL] 내게 와 투 포인터

0. 내게 와 제발..

전에 코테를 볼 때 '아 이 문제 투 포인터로 푸는 거 같은데'라는 생각이 들었으나, 코드가 기억이 안 나서 다른 방법으로 푼 적이 있다. 테스트 케이스는 맞았지만 아마 효율성 테스트에서 망했겠지 그 코드는... 그러고 나서 분명 투 포인터 알고리즘을 한 번 더 훑었는데.. 왜 이번에도 기억이 안 났을까...? 난 바보다... 그렇지만 두 번째니까 다음부턴 기억나겠지..

내게와 내게와 My Two Pointer

 

1. 99클럽 Python 미들러 문제 풀이

[프로그래머스 / 연습문제 / Lv2. 연속된 부분 수열의 합]

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

프로그래머스

 

비내림차순으로 정렬된 수열 리스트 sequence에서 합이 k가 되는 부분 수열을 찾아 시작 인덱스와 끝 인덱스를 리턴하는 문제였다. 해당되는 부분 수열이 여러 개라면, 길이가 짧은 것을 우선으로, 길이도 같다면 인덱스가 작은 것을 우선으로 리턴한다.

 

# 처음에 생각한 풀이 방식

 

처음에는 누적합 방식으로 풀이를 생각했다. 누적합 리스트를 생성한 후, 각 인덱스의 요소 차와 k를 비교하여 가장 짧은 부분 수열의 인덱스를 리턴했다. 그러나 테스트 케이스는 모두 맞았지만 역시나 시간복잡도에서 걸리고 말았다.

 

분명 비슷한 문제를 풀어봤던 것 같은데 가물가물해서, 전에 [이것이 코딩테스트다]를 통해 알고리즘을 공부하며 정리했던 코드를 확인해 봤는데... 그냥 이 문제 그 잡채.. 난 멍청이 었다.. 이 문제는 투 포인터를 사용하는 대표 예제 같은 문제였음을..... 이렇게 된 거 투 포인터 개념을 복습하자..!

 

# 투 포인터(Two Pointers)란?

 

- 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘

- '시작점'과 ' 끝점' 2개의 점으로 접근할 데이터 범위 표현

 

특정한 부분합이 k일 때

 

1) 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 함

2) 현재 부분합이 k와 같다면 인덱스 기록

3) 현재 부분합이 k보다 작으면 end += 1

4) 현재 부분합이 k보다 크거나 같으면 start += 1

5) 모든 경우를 확인할 때까지 2~4번 과정 반복

 

투 포인터 알고리즘의 특징은 시작점을 오른쪽으로 이동시키면 항상 합이 감소, 끝점을 오른쪽으로 이동시키면 항상 합이 증가한다. 고로 수열 내 원소에 음수 데이터가 있다면 사용 불가!

 

투 포인터 알고리즘은 시작점 혹은 끝점 둘 중 하나가 + 1이 되는 루프를 n번 돌기 때문에 시간복잡도가 O(N)이다.

이걸 코테에서 중첩 반복문으로 풀었으니 당연히 효율성 테스트에서 걸리지 ㅜ

 

다음은 투 포인터 알고리즘을 이용한 풀이 소스코드이다!

# 투 포인터를 이용한 구간 합 구하기 문제 풀이
def solution(sequence, k):
    
    n = len(sequence)
    interval_sum = 0
    end = 0
    
    min_value = int(1e9)
    answer = []
    for start in range(n):
        while interval_sum < k and end < n:
            interval_sum += sequence[end]
            end += 1
        
        if interval_sum == k:
            if end - start < min_value:
                min_value = end - start
                answer = [start, end - 1]
        interval_sum -= sequence[start]

                    
    return answer

 

2. 회고

역시 인간은 망각의 동물... 그렇지만 계속 반복하다 보면 언젠간 척하면 척으로 코드가 술술 나오지 않겠어요? 멀지 않았다... 알고리즘 공부 Keep Going 아자자! 다음엔 바로 풀어줄게!