다중 포인터 패턴

한 개의 포인터가 이동하며 조건에 부합하는 값을 찾는 것이 아니라 여러 개의 포인터를 사용하여 값을 찾아내는 방식

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


sumZero([-4,-3,-2,-1,0,1,2,5])
// 이렇게 하나의 포인터만 사용하여 값을 찾게되면 하나의 원소를 기준으로 n번을 돌아야 할 수도 있다.
// 입력 데이터가 크면 문제가 된다.

 

아래는 포인터를 투 개 사용한 투 포인터 방식이다. 포인터를 시작 지점과 끝 지점, 두 개를 사용하여 중앙을 향해 범위를 좁혀오는 방식이다. 단, 배열이 정렬돼 있어야 한다.

// 배열이 정렬돼 있어야함.
function sumZero(arr) {
    let left = 0;
    let right = arr.length - 1;
    while(left < right) {
        let sum = arr[left] + arr[right];
        if(sum === 0) {
            return [arr[left], arr[right]];
        } else if(sum > 0) {
            right--;
        } else {
            left++;
        }
    }
}

 

 

예제) 고윳값의 개수

다중 포인터 - countUniqueValues
정렬된 배열을 받아들이고 배열의 고유 값을 세는 countUniqueValues라는 함수를 구현합니다. 배열에 음수가 있을 수 있지만 항상 정렬됩니다.

countUniqueValues([1,1,1,1,1,2]) // 2
countUniqueValues([1,2,3,4,4,4,7,7,12,12,13]) // 7
countUniqueValues([]) // 0
countUniqueValues([-2,-1,-1,0,1]) // 4
Time Complexity - O(n)

Space Complexity - O(n)

보너스

상수 또는 O(1) space 와 O(n) time으로만 이 작업을 수행해야 합니다.

 

강의 듣고 내가 푼 답

// function countUniqueValues(arr){
//   return [...new Set(arr)].length;
// }

function countUniqueValues(arr) {
    
    const sortedArr = arr.sort((a, b) => a - b);
    
    if (arr.length === 0) return 0;
    
    let i = 0; 
    let j = 1;
    
    while( j < sortedArr.length) {
        if (sortedArr[i] === sortedArr[j]) {
            j++; 
        } else {
            
            i++;
            sortedArr[i] = sortedArr[j]
        }
    }
    
    return i+1; // 새로운 값을 할당한 자리의 인덱스는 개수보다 하나 작으므로 +1
}
// 포인터가 중앙을 향해 이동하는 것이 아니라 같은 방향으로 이동한다.
// 배열이 정렬돼 있지 않으면 같은 값이 인덱스를 달리하여 기록될 수 있으므로 정렬해야 한다.

 

강사 코드

function countUniqueValues(arr){
    if(arr.length === 0) return 0;
    var i = 0;
    for(var j = 1; j < arr.length; j++){
        if(arr[i] !== arr[j]){
            i++;
            arr[i] = arr[j]
        }
    }
    return i + 1;
}
countUniqueValues([1,2,2,5,7,7,99])

 

 

 

예제)

다중 포인터 - averagePair
averagePair라는 함수를 작성합니다. 정렬된 정수 배열과 목표 평균이 주어졌을 때, 배열에 쌍의 평균이 목표 평균과 같은 값의 쌍이 있는지 확인합니다. 목표 평균과 일치하는 쌍이 두 개 이상 있을 수 있습니다.

보너스 제약조건:

Time: O(N)

Space: O(1)

예시 인풋:

averagePair([1,2,3],2.5) // true
averagePair([1,3,3,5,6,7,10,12,19],8) // true
averagePair([-1,0,3,4,5,6], 4.1) // false
averagePair([],4) // false

 

내 풀이

function averagePair(sortedArr, avg){
    // 입력배열이 정렬돼 있다고 가정. 이 방법은 정렬돼 있어야 사용 가능하다.
    // 두 개를 더해 2로나눈 값이 avg보다 크다면 
    // right를 감소시킨다. 정렬돼 있으므로 더 작은 값이어야 나눈 값이 줄어들 테니까
    // 만약 값이 avg보다 작다면 left를 증가시킨다. 그래야 좀 더 커질 테니까

    let left = 0;
    let right = sortedArr.length -1;
    
    while ( left < right) {
        let dividedVal = (sortedArr[left] + sortedArr[right]) / 2
        if( dividedVal === avg) return true;
        
        if (dividedVal > avg) right--
        if (dividedVal < avg) left++
    }
    
    return false;
    
    
}