[프로그래머스] 타겟 넘버 (Javascript)

문제

[프로그래머스] 타겟 넘버

풀이 과정

• 이 문제는 처음엔 BFS를 사용해서 풀어보려고 했다.

// BFS
function solution(numbers, target) {
    let n = numbers.length;
    let queue = [[0, 0]];
    let answer = 0;
    while (queue.length) {
        let [v, depth] = queue.shift();
        if (depth < n) {
            queue.push([v + numbers[depth], depth + 1]);
            queue.push([v - numbers[depth], depth + 1]);
        }
        if (depth === n && v === target) answer++;
    }
    return answer;
}

하지만 이렇게 하니 테스트 케이스 1,2번이 시간 초과가 발생했다.
최악의 경우(n=20)일 경우 시간 초과가 발생하는듯 하다.
실제로 vscode에서 n=16으로 설정해놓고 돌리니 실행 시간은 5초가 넘게 걸렸고 n=17 일때는 16초가 넘게 걸렸다.
그래서 다른 분들의 코드를 참고하니 다들 DFS로 풀길래 이번엔 DFS로 코드를 구현해보았다.

// DFS
function solution(numbers, target) {
    let n = numbers.length;
    let answer = 0;
    function dfs(sum, depth) {
        if (depth < n) {
            dfs(sum + numbers[depth], depth + 1);
            dfs(sum - numbers[depth], depth + 1);
        } else {
            if (sum === target) answer++;
            return;
        }
    }
    dfs(0, 0);
    return answer;
}

위 코드를 제출하니 통과했다.

하지만 아직도 의문이다.
내가 보기에는 두 코드 전부 O(2N)의 시간 복잡도를 가지는 것 같은데, 왜 코드 수행 시간은 다른지가 의문이다.

이 부분은 좀 더 알아봐야 겠다.

-----해결-----

BFS로 했을 때 시간초과가 발생한 이유를 알았다.
shift()메서드는 배열의 맨 앞에 요소를 제거한 뒤 나머지 요소를 재정렬 하기 때문에 O(N)의 시간복잡도가 든다.
따라서 직접 Queue 자료구조를 구현해줌으로써 맨 앞의 요소를 제거할 때 O(1)의 시간복잡도가 들도록 바꾸면 된다.

코드

class Queue{
    constructor(){
        this.storage = {};
        this.front = 0;
        this.rear = 0;
    }
    size(){
        // 큐가 비어있을 경우
        if(this.storage[this.rear] === undefined) return 0;
        return this.rear-this.front+1;
    }
    dequeue(){
        let temp = this.storage[this.front];
        delete this.storage[this.front];
        
        if(this.front === this.rear) {
            this.front = 0;
            this.rear = 0;
        } else{
          this.front++;  
        }
        return temp;
    }
    enqueue(value){
        if(this.size()===0){
            this.storage["0"] = value;
        } else{
            this.rear++;
            this.storage[this.rear] = value;
        }
    }
}

// BFS
function solution(numbers, target) {
    let n = numbers.length;
    let queue = new Queue();
    queue.enqueue([0,0]);
    let answer = 0;
    while (queue.size()) {
        let [v, depth] = queue.dequeue();
        if (depth < n) {
            queue.enqueue([v + numbers[depth], depth + 1]);
            queue.enqueue([v - numbers[depth], depth + 1]);
        }
        if (depth === n && v === target) answer++;
    }
    return answer;
}

혹은 메모리 제한이 넉넉하다면 배열을 사용하되 shift()메서드를 사용하지 말고front 만 움직여줌으로써 메모리는 조금 더 사용하되 아래처럼 간결하게 구현할 수 있다.

// BFS
function solution(numbers, target) {
    let n = numbers.length;
    let queue = [[0, 0]];
    let front = 0;
    let answer = 0;
    while (queue.length) {
        if(front >= queue.length) break; // front가 범위를 벗어나면 중단하기
        let [v, depth] = queue[front];
        front++;
        if (depth < n) {
            queue.push([v + numbers[depth], depth + 1]);
            queue.push([v - numbers[depth], depth + 1]);
        }
        if (depth === n && v === target) answer++;
    }
    return answer;
}

왜 사람들이 BFS로 안하고 DFS로 풀었는지 이제야 알겠다.
자바스크립트에선 queue자료구조를 지원해주는 내장 모듈이 없기 때문에 BFS로 문제를 풀려면 직접 queue를 구현해줘야 한다.
이는 코드를 길어지게 만들고 시간이 많이 소모되는 작업이다.
따라서 다른 사람들처럼 DFS로 푸는 것이 더 현명한 선택이였던 것 같다.