[알고리즘] 다중 포인터 패턴: 고유값 세기 (countUniqueValues)

[알고리즘] 다중 포인터 패턴: 고유값 세기 (countUniqueValues)

https://y-chyachya.tistory.com/142

위의 내용과 같이 다중 포인터나 투 포인터 패턴을 사용해서 해결할 수 있습니다.

다만 위와 다른것은 처음과 끝에서 가운데로 이동하는게 아닙니다.

그래도 마찬가지로 두개의 포인터를 사용한다는 것이 관건입니다.

조건에 따라 두 포인터가 특정 방향으로 이동하도록하고 정해진 배열의 개수를 반환합니다.

 

 

countUniqueValues([1, 1, 1, 1, 2, 2,]); // 2
countUniqueValues([]) // 0
countUniqueValues([1, 2, 3, 4, 5, 6, 6, 6, 8]) // 7

 

 

 

 

힌트

위의 설명에 덧붙이자면

루프를 돌면서 1부터 j는 루프대로 증가한다.

그러면서 i는 0부터 j와 비교하여 같다면 그대로, 다르다면 +1 증가 시키고 그 자리에 당시의 j 값을 넣어준다.

 [1, 2, 3, 4, 5, 3, 4, 4, 5, 6]

이런 배열이 만들어지게 된다.

i의 자리만큼 배열이 고유값으로 만들어지게 됨으로. i까지의 length 즉 i + 1을 리턴해주면 된다.

 

 

 

 

O(n) 시간 복잡도 해결책

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;
}

 

 

 

 

 

 

참조!

https://www.udemy.com/course/best-javascript-data-structures/?couponCode=ST9MT71624