728x90
반응형
[알고리즘] 다중 포인터 패턴: 고유값 세기 (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
728x90
반응형
'알고리즘' 카테고리의 다른 글
[알고리즘] 핼퍼 메소드 재귀 (Helper Method Recursion) (0) | 2024.07.19 |
---|---|
[알고리즘] 재귀 (Recursion) (0) | 2024.07.19 |
[알고리즘] 기준점 간 이동 배열 패턴 (Sliding Window) (0) | 2024.07.11 |
[알고리즘] 다중 포인터 패턴 (Multiple Pointers) (0) | 2024.07.10 |
[알고리즘] 빅오 표기법 (Big O Notation) (0) | 2024.07.06 |
댓글