투 포인터 알고리즘

 

투 포인터 알고리즘은 배열 또는 리스트에서 두 개의 포인터를 사용하여 원하는 결과를 찾는 알고리즘 기법입니다. 이 알고리즘은 주로 선형 시간(O(N))에 문제를 해결하는 효율적인 방법으로 사용됩니다. 특히, 정렬된 배열이나 리스트에서 특정한 조건을 만족하는 요소를 찾거나, 부분 배열 또는 부분 리스트를 찾는 데 유용합니다.

투 포인터 알고리즘은 일반적으로 다음과 같은 두 가지 포인터를 사용합니다:

1. 시작 포인터(Left Pointer): 배열이나 리스트의 시작 위치를 가리킵니다.
2. 끝 포인터(Right Pointer): 배열이나 리스트의 끝 위치를 가리킵니다.

이 두 포인터는 주로 다음과 같은 방식으로 조작됩니다:

1. 시작 포인터와 끝 포인터가 서로 다른 요소를 가리키며, 이들을 이용하여 특정한 조건을 만족하는 구간을 탐색합니다.
2. 두 포인터를 이동시키면서 조건을 확인하고, 조건에 따라 포인터를 적절히 조작합니다.

투 포인터 알고리즘은 일반적으로 배열이나 리스트가 정렬되어 있는 경우에 많이 사용됩니다. 이 알고리즘을 사용하면 선형 시간 내에 원하는 요소를 찾거나 부분 배열을 탐색할 수 있습니다. 투 포인터 알고리즘은 효율적이고 직관적인 방법으로 문제를 해결할 수 있는 장점을 가지고 있습니다.

 

 

 

 

 

 

 

 

 

 

 

---

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

 

 

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        int[][] dp = new int[sequence.length][];
        boolean flag = false;
        for(int i=0; i<sequence.length; i++) {
            dp[i] = new int[sequence.length-i];
            for(int j=0; j<sequence.length-i; j++) {
                for(int x=j; x<j+i+1; x++) {
                    dp[i][j] += sequence[x]; 
                }
                if(dp[i][j] == k) {
                    answer[0] = j;
                    answer[1] = j+i;
                    flag = true;
                    break;
                }
                if(flag) { 
                    break;
                }   
            }
            if(flag) { 
                break;
            }  
        }
        return answer;
    }
}

 

 

 

 

 

역시나 위 코드는 for 문이 3개나 있어서 시간 초과 오류가 발생한다.

 

---

아래는 투 포인터 알고리즘을 사용한 결과이다. for 문이 하나밖에 없어서 시간 복잡도가 선형으로 증가한다.

 

 

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        
        int left = 0;
        int ans1 = 0;
        int ans2 = 0;
        int size = sequence.length;
        int sum = 0;
        
        for(int right=0; right<sequence.length; right++) {
            sum += sequence[right];
            
            while(sum>k) {
                sum -= sequence[left];
                left++;
            }
            
            if(sum==k) {
                if(size > right-left) {
                    size = right-left;
                    ans1=left;
                    ans2=right;
                }
                else {
                    ans1=Math.min(ans1, left);
                    ans2=Math.min(ans2, right);
                }
            }
        }
        
        return new int[] {ans1, ans2};
    }
}