자바스크립트로 알고리즘 풀기

여지껏 자바 언어로 알고리즘 문제를 풀었다.

 

첫 웹 개발을 자바로 배워서 스프링 개발자를 희망했기에 C++로 풀던 알고리즘을 자바로 변경했었다.

 

백준 알고리즘 강의를 들었을 때에도 자바로 배워서 다른 언어로 풀 생각을 하지 않았다.

 

근데 부스트캠프를 수강하고, 노드 개발자가 되겠다고 생각을 굳힌 요즘 문득 이런 생각이 들었다.

 

'노드 개발자로 취업을 하면 실무에서도 자바스크립트나 타입스크립트를 쓸텐데 자바스크립트에 익숙해져야 하지 않을까?'

 

그래서 지금부터라도 자바스크립트로 문제를 풀려고 한다.

 

무엇보다 긴 시간동안 자바로만 알고리즘을 풀어서 약간 매너리즘을 느꼈는데 자바스크립트로 풀어보니 신선하야 새로운 매력이 있다.

 

공교롭게도 지금 읽고 있는 알고리즘 책이 자바로 쓰였지만 알고리즘이라는 것은 언어에 크게 구애받지 않으니까 그러려니 한다.

 

그런고로 자바스크립트로 문제를 풀면서 새로 알게되는 자바와 자바스크립트의 차이를 여기에 정리해보려 한다.

---

1. 문자 - 'A' 불가능

자바에서는 보통 문자를 숫자로 변경할 때 - 'A'를 많이 사용한다. 그러면 문자가 아스키코드값으로 자동 변환되고 연산이 수행된다.

 

허나 자바스크립트에서는 문자 - 'A'를 하면 NaN이 나온다. 그러면 어떻게 해결해야 할까?

 

charCodeAt()

다른 방법도 많겠지만 나는 위 함수를 사용했다. charCodeAt()은 문자의 유니코드를 반환한다. 따라서 다음처럼 사용할 수 있다.

 

'B'.charCodeAt() - 'A'.charCodeAt()

 

결과는 1이 나온다.

 

 

2. undefined

자바에서는 배열의 크기보다 큰 인덱스를 참조하면 IndexOutOfBounds 예외를 던진다. 

 

하지만 자바스크립트는 undefined를 출력할 뿐이다.

 

아래 프로그래머스의 Lv1 문제를 보자.

https://school.programmers.co.kr/learn/courses/30/lessons/159994

 

카드 뭉치가 2개 있고, 가장 위의 카드만을 순서대로 뽑아 goal 배열의 문자열을 만들 수 있느냐다.

 

나는 당연히 자바처럼 풀었다.

function solution(cards1, cards2, goal) 
{
    let id1 = 0;
    let id2 = 0;
    let idg = 0;

    while(id1 < cards1.length && id2 < cards2.length && idg < goal.length) 
    {
        if(goal[idg] === cards1[id1])
            id1++;
        else if(goal[idg] === cards2[id2])
            id2++;
        else
            return "No";

        idg++;
    }

    while(id1 < cards1.length && idg < goal.length)
    {
        if(goal[idg] === cards1[id1])
            id1++;
        else
            return "No";

        idg++;
    }

    while(id2 < cards2.length && idg < goal.length)
    {
        if(goal[idg] === cards2[id2])
            id2++;
        else
            return "No";

        idg++;
    }

    return idg === goal.length ? "Yes" : "No";
}

 

하지만 shift()와 undefined를 이용해서 아래처럼 아름답게 풀 수 있다.

function solution(cards1, cards2, goal) 
{
    for(const g of goal)
    {
        if(g === cards1[0])
            cards1.shift();
        else if(g === cards2[0])
            cards2.shift();
        else
            return "No";
    }
    
    return "Yes";
}

 

3. /는 정수가 아닌 소수를 반환한다.

오늘 이것때문에 2시간을 헤맸다.

 

분명 맞는데 정답이 아니어서 같은 문제를 자바로 풀었는데 맞았다.

 

헤맸던 포인트는 다음과 같다.

let endTime = tmp + 10;
if(endTime % 100 >= 60)
	endTime = endTime / 100 * 100 + 100 + endTime % 10;

 

위 코드를 자바로 풀면 정수형이기 때문에 endTime / 100에서 소수점을 버리지만, 자바스크립트는 타입이 없기 때문에 소수점을 포함한다.

 

4. shift, unshift는 효율이 구데타마다.

shift와 unshift는 배열의 앞에서 작업을 하기 때문에 인덱스의 모든 요소를 옮기는 작업이 필요하다. 따라서 O(n)의 시간 복잡도를 가진다.

 

pop과 push는 배열의 뒤에서 작업을 하기 때문에 옮기는 작업이 불필요하다. 따라서 O(1)의 시간 복잡도를 가진다.

 

그래서 큐를 사용해야 하는 문제를 마주했을 때, push와 shift를 사용하면 시간 초과가 발생할 수 있다.

 

그럴 경우 큐를 직접 구현하는 것이 좋다. 큐 구현은 간단하다.

class Queue
{
    constructor()
    {
    	this.items = {};
        this.front = 0;
        this.rear = 0;
    }
    
    enqueue(item)
    {
    	this.items[this.rear++] = item;
    }
    
    dequeue()
    {
    	const ret = this.items[this.front];
        delete this.items[this.front++];
        return ret;
    }
    
    isEmpty()
    {
    	return this.rear - this.front === 0;
    }
}

 

5. 힙을 사용해야 할 때

자바스크립트로 코테를 풀면 굉장히 자바가 마려워지는 순간이 온다. 예를 들어 우선순위 큐를 사용해야 할 때.

 

다른 언어는 라이브러리로 여러 자료구조를 제공해주지만, 자바스크립트는 그렇지 않다. 강한 자만이 살아남을 수 있는 언어인 것이다.

 

힙의 구현법은 동작만 알고 있으면 그렇게 어렵지 않다. 배열로 구현할 수 있다.

 

힙은 요소를 넣고 뺄 때마다 정렬이 일어난다. 트리 구조로 되어 있기 때문에 정렬은 O(n log n)의 시간 복잡도를 가진다.

 

동작은 여기 저기 정리된 곳이 많으니, 최대 힙의 구현을 정리할 것이다.

 

우선 힙의 요소에 해당하는 Node를 만들어 보자.

class Node
{
    constructor(item, priority)
    {
    	this.item = item;
        this.priority = priority;
    }
}

값은 물론, 우선 정도를 나타내는 priority를 가진다.

 

이제 이 요소를 담을 최대 힙을 만들어 보자.

class MaxPriorityQueue
{
    constructor()
    {
    	this.arr = [];
    }
    
    enqueue(item, priority)
    {
    	const node = new Node(item, priority);
        this.arr.push(node);
        heapifyUp();
    }
    
    heapifyUp()
    {
    	let id = this.arr.length - 1;
        const node = this.arr[id];
        
        while(id > 0)
        {
        	// 부모 선정
        	const parentId = Math.floor((id - 1) / 2);
        	const parent = this.arr[parentId];
            
            // 부모보다 우선도가 높을 때만 교체
        	if(node.priority <= parent.priority)
            	break;
            
            this.arr[parentId] = node;
            this.arr[id] = parent;
        	id = parentId;
        }
    }
    
    dequeue()
    {
    	const ret = this.arr[0];
        const end = this.arr.pop();
        
        // 요소가 있을 때만 힙 정렬 수행
        if(this.arr.length > 0)
        {
        	this.arr[0] = end;
        	heapifyDown();
        }
        
        return ret;
    }
    
    heapifyDown()
    {
    	let id = 0;
        const node = this.arr[id];
        
        while(true)
        {
            let leftChildId = 2*id + 1;
            let rightChidId = 2*id + 2;
            let leftChild = null;
            let rightChild = null;
        	let swapId = null;
            
            if(leftChildId < this.arr.length)
            {
            	leftChild = this.arr[leftChildId]
                
                // 왼쪽 자식의 우선도가 부모보다 높으면 교체 후보로 설정
                if(node.priority < leftChild.priority)
                    swapId = leftChildId;
            }
            
            if(rightChildId < this.arr.length)
            {
                rightChild = this.arr[rightChildId];
                
                // 오른쪽 자식의 우선도가 부모보다 높거나, 왼쪽 자식보다 높으면 교체 후보로 설정
                if(
                (swapId === null && node.priority < rightChild.priority) ||
                (swapId !== null && leftChild.priority < rightChild.priority))
                {
                    swapId = rightChildId;
                }
            }
            
            if(swapId === null)
            	break;
                
            this.arr[id] = this.arr[swapId];
            this.arr[swapId] = node;
            id = swapId;
        }
    }
}

정말 길다. 

 

최소 힙을 만드려면 부등호들을 바꿔주면 되지만 야매로 하는 방법이 있다. 각 요소를 만들 때 우선도에 -를 붙여 음수로 만들면 된다.