알고리즘 복잡도, 비트 연산자

오늘 스터디에서 알고리즘 복잡도와 비트 연산자를 공부했다. Big O 는 원래 알고 있던 개념이긴 했지만 이번에 실제로 알고리즘 문제를 풀면서 공간 복잡도, 시간 복잡도를 따져봤다.

344. Reverse String 이 문제를 풀었다.

reverse 함수를 쓰면 참 쉬웠지만…
아까 풀때는 새로운 배열을 만들어서 복사해놓고 빼면서 아규먼트로 받은 배열을 바꿔줬는데 그렇게 했더니 O(N^2) 복잡도가 나왔다.
swap해주면 되는거였고, 이렇게 하면 O(N) 복잡도가 나온다.

공간 복잡도는 변수 하나를 할당하는 갯수라고 생각하면 된다고…

그 다음으로는 136. Single Number 이 문제를 풀었다.
평소처럼 객체를 만들어서 풀었는데, 좀 더 멋있는 방법을 알았다.
XOR 연산자를 이용하는 것이다.

요런걸 배웠는데, AND는 곱하기 느낌이고 OR은 더하기 느낌이라고..
XOR은 처음 알게 되었는데, 같으면 0 다르면 1이다.

var singleNumber = function(nums) {
    let num = 0;
    for(let i = 0; i < nums.length; i++) {
        num = num ^= nums[i];
    }
    return num;
};

이렇게 겁나 멋있게 문제를 풀었다! 얏 호!