countUniqueValues 문제풀이

내 풀이

• 1. 집합으로 풀기.
• 2. 투포인터로 풀기.

/*
문제
	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.
 */

// 풀이 1: 집합으로 풀기.
function countUniqueValue(arr) {
    let set = new Set(arr);
    return set.size;
}

console.log(countUniqueValue([1, 1, 1, 1, 1, 2]));
console.log(countUniqueValue([1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13]));
console.log(countUniqueValue([]));
console.log(countUniqueValue([-2, -1, -1, 0, 1]));

// 풀이 2: 투 포인터로 풀기.

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

console.log(countUniqueValue_([1, 1, 1, 1, 1, 2]));
console.log(countUniqueValue_([1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13]));
console.log(countUniqueValue_([]));
console.log(countUniqueValue_([-2, -1, -1, 0, 1]));

둘다 O(N)으로 나쁘지않다.
집합으로 푸는 방법을 처음에 생각했는데, 쉽지만 알고리즘적인 풀이가 아닌 것 같다.
하지만, 간단하게 풀리니까 Set을 잘이용하면 괜찮을 것 같다.

참고로 Set 연산의 시간 복잡도는 다음과 같을 것이다.

O(n)

new Set([n])
set.keys()
set.values()
set.entries()
set.forEach()

O(1)

set.add(v)
set.delete(v)
set.has(v)