Multiple Pointers - countUniqueValues(고유값세기 - 다중포인터)

문제

Implement a function called countUniqueValues, which accepts a sorted array, and counts the unique values in the array. There can be negative numbers in the array, but it will always be sorted.
정렬이 되어있는 배열에서 고유의 값들의 갯수를 세는 함수를 실행하라. 배열에는 음수가 있을 수 있으나 항상 정렬이 되어있다.

Examples:
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

Note:
Time Complexity - O(n)
Space Complexity - O(n)

 

나의 코드

• 시간복잡도는 O(n) 이어야 하므로 for 문이 이중이면 안된다.
• 이중포인터(i,j)를 가지고 값을 비교해가며 두 값이 다를 경우에 j값을 i+1값에 넣어가며 전진한다.

 

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

}

console.log(countUniqueValues([1,1,1,1,1,2]))

강의에서의 정답

• 나의 코드는 문제에서의 조건, 결과가 맞았다.
• 그러나 for문 안에서 j와 arr의 길이를 비교하는 조건문은 필요가 없었다. 어짜피 j는 arr끝까지 가야 탐색이 끝나는 것이기때문에 필요없는 구문을 넣었다는 점이 아쉬웠다.
• 그리고 for문 안에서 i도 ++을 먼저했으면 되는데, i값을 증가시키는 연산을 두번이나 한 셈이어서 이것도 수정하는 것이 좋겠다.

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])

 

강의 : https://www.udemy.com/share/106X8E3@Lt-njJ7uYB8WJ1Fa57QDkC-Jt8Jccl8YSfNg-Ss97_zbUJPT4bPNz4Cynqye826R/