투 포인터 알고리즘이란 ? (프로그래머스 - 연속된 부분 수열의 합)

투포인터 알고리즘 

 

- 리스트에 순차적으로 접근해야 할 때 두 개의 점(시작점 , 끝점)의 위치를 기록하면서 처리하는 알고리즘이다.

 

- 시작점과 끝점으로 접근할 데이터의 범위를 표현할 수 있다.

 

예를 들어, 해당 수열에서 합이 5인 부분 수열의 개수를 찾는다고 생각해보자

 

 

1

2

3

2

5

 

완전 탐색으로 문제를 해결할 수도 있지만 너무 많은 시간이 걸린다는 단점이 있다.

 

따라서 이때 투포인터 알고리즘을 이용하여 문제를 해결할 수 있다.

 

투포인터 알고리즘의 방식은 다음과 같다.

 

1. 처음에는 시작점과 끝점 모두 0에서 시작한다.

 

1(start,end)

2

3

2

5

 

2. 합이 목표값과 같으면 카운트한다.

 

3. 만약 목표값보다 부분수열의 합이 작다면 end 인덱스를 1 증가시킨다.

 

1(start)

2(end)

3

4

5

 

3-1. 현재 부분 수열의 값은 3이므로 end 인덱스를 1만큼 더 증가시킬 수 있다. 

         그렇게되면 부분 수열의 값은 6이 된다.

 

4. 만약 목표값보다 부분수열의 합이 크다면 start 인덱스를 1만큼 증가시킨다.

 

1

2(start)

3(end)

4

5

  

5. 모든 경우를 확인 할때까지 2~4 과정을 반복한다.

 

이렇게 함으로써 합이 5가 되는 부분 수열을 모두 구할 수 있다 !

 

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

 

 

 

투 포인터를 활용하여 풀 수 있는 대표적인 문제이다

 

분석

합이 k 가 되는 부분 수열의 시작 인덱스와 마지막 인덱스를 구해야 한다.

따라서 투포인터 알고리즘을 이용하면 모든 경우를 구할 수 있다.

 

그리고 인덱스의 길이를 비교해서 가장 최소 일 때를 반환해주면 된다.

 

코드

class Solution {
    
    public int[] solution(int[] sequence, int k) {
        int min = Integer.MAX_VALUE;
        int end = 0;
        int num = sequence.length;
        int sum = 0;
        int[] answer = new int[2];
        
        for(int start=0;start<num;start++){
            while(sum < k && end < num){
                sum += sequence[end];
                end ++;
            }
            
            if(sum == k && min > (end-1) - start) {
                min = (end-1) - start;
                answer[0] = start;
                answer[1] = end-1;
            }
            
            sum -= sequence[start];
        }
        
        return answer;
    }
}

 

 

"이것이 취업을 위한 코딩 테스트다 with 파이썬" 내용을 기반으로 제작하였습니다.

https://www.youtube.com/watch?v=ttLRltNDiCo