[알고리즘] Two Pointers

투포인터 (Two Pointers)

두개의 포인터로 정돈되어있는 배열에서 원하는 값을 찾을 때 사용하면 좋은 알고리즘

 

 

 

그냥 반복문을 쓰다보면 시간 초과가 걸리는 경우가에 있는데, 투 포인터를 사용하면 메모리와 시간 효율성을 높일 수 있습니다. 코딩 테스트를 보면 시간 복잡도를 낮출 수 있는 경우에는 일부로 테스트 케이스에 n이 정말 큰 (엄청 긴 배열이나 문자열)을 사용해서 Time out을 걸리게 하는 케이스가 많다고...

 

 

 

우선 아래의 문제를 제가 일반적으로 풀수있는 방법으로 풀어보았고 그 밑에 투포인터 방식으로 풀이된 문제입니다.

 

주어진 배열에서 중복된 값을 제거한 특수한 값이 몇개인지 리턴하는 문제!

countUniqueValues([1, 1, 1, 2, 1])    -->  2
countUniqueValues([1, 1, 2, 15])    -->  3
countUniqueValues([ ])  --> 0

 

 

function countUniqueValues(arr){
    let result = 0;
    let newArr = [];
    
    // 배열의 길이가 0이라면 0으로 리턴 
    if(arr.length == 0){
        return result;
    }
    
    for(let i=0; i<arr.length; i++){
       // 새로운 배열에 해당 값이 없으면 push
        if(!newArr.includes(arr[i])){   
            newArr.push(arr[i]); 
        }
    }
    return result;
}
var arr = [1, 1, 1, 2, 4];
countUniqueValues(arr);

 

위에 제가 풀어본 방식은 우선 새로운 배열을 담을 수 있는 변수를 만들어주고 배열의 길이가 0이라면 result를 리턴합니다. 그리고 for루프문에서 만약 newArr 새로운 배열에 기존배열의 i 인덱스 값이 들어가 있지않다면 push 해줍니다. 이렇게 새로운 배열에 중복된 값이 없이 특수한 값만 들어가게 됩니다.

 

 

그리고 아래는 투포인터로 해결된 문제풀이!

투포인터는 둘다 양쪽끝에서 중간으로 만나는 방법도 있고 다양하지만 이번 문제는 배열의 왼쪽 끝에서 오른쪽으로 움직입니다!

 

function countUniqueValues(arr){
    if(arr.length == 0){
        return 0;
    }
    
    let i=0;

    for(let j=1; j<arr.length; j++){
        if(arr[i] !== arr[j]){
            i++;
            arr[i] = arr[j];
        }
    }
    return i + 1;
}

var arr = [1, 1, 1, 2, 3, 5, 7];
countUniqueValues(arr);

 

 

i와 j의 두 포인터가 돌개되는데 i는 0부터 시작하고, j는 for문에서 1부터 증가시켜 줍니다. 만약에 i번째와 j번째의 값이 동일 하다면 j는 어떠한 행동도 취하지 않고 그대로 1씩 증가하면서 이동합니다. 그러다가 i번째와 다른 값을 발견하게되면 i에 1을 더해주고 해당 인덱스 값에 j의 값으로 치환해줍니다. 그러다가 j가 for문을 끝내게 되면 i의 인덱스 값에 +1을 해주면 고유한 값의 갯수를 리턴해주는 것! 그리고 하나의 for문만 돌면되기 때문에 시간복잡도는 O(n)을 갖게 됩니다.

 

i=0, j=1부터 배열의 왼쪽부터 오른쪽으로 이동

 

j가 이동하면서 i의 값과 다른 값을 찾으면 i++해주고 해당 자리에 j의 값으로 치환