[프로그래머스/JS] Lv1. 같은 숫자는 싫어

문제

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

프로그래머스

 

---

풀이

 자바 스크립트로 큐를 구현해보고자 시도한 문제였다. 자바스크립트에는 자바처럼 큐 라이브러리가 없기 때문에 직접 구현을 해야만 한다.

 

 스택의 성질을 써도 되지만, 나는 자료구조에서 값을 빼내어 answer 변수에 저장할 때, 그냥 큐에서 poll 하는 순서대로 저장하고 싶었다.

 

 그래서 큐를 구현하였고, 제출했더니 시간초과가 발생했다.

function solution(arr)
{
    var answer = [];
    
    let queue = new Queue();
    for(let i = 0; i<arr.length;i++){
        const num = arr[i];
        if(queue.peek()!==num){
            queue.add(num);
        }
    }
    while(!queue.isEmpty()){
        answer.push(queue.poll());
    }
    return answer;
}

class Queue{
    
    constructor(){
        this.arr = [];
    }
    poll(){
        return this.arr.shift();
    }
    add(item){
        this.arr.push(item)
    }
    peek(){
        return this.arr[this.arr.length-1];
    }
    isEmpty(){
        return this.arr.length===0;
    }
}

 

 

띠용.. 제한 사항에 배열 'arr의 크기 : 1,000,000 이하의 자연수'라는 것을 간과했던 탓일까. 정확한 시간 제한 기준이 명시되어있지 않아 저렇게 연습해보라는 문제인줄 알았다.

 

 

이 코드에서 가장 큰 오버헤드는  queue를 구현한 부분의 poll()에서 shift 메서드 부분이다. shift를 쓸 때마다 배열은 한 칸씩 당겨지며, O(n)의 시간복잡도가 생기게 된다.

 

 그리고 while문을 돌며, queue에서 정답 배열로 값을 밀어넣는 과정도 O(n)의 시간복잡도가 생기게 된다.

 

 

 

 

 

그래서 queue 자료구조 구현없이 스택의 원리만 가져와 구현했더니 또 시간초과가 발생했다.

function solution(arr)
{
    let stack = [];
    for(let i = 0; i<arr.length;i++){
        const num = arr[i];
        if(stack.length===0||stack[stack.length-1]!==num){
            stack.push(num);
        }
    }
    return stack;
}

 

시간복잡도는 최소화했는데, 로직적으로 미세하게 시간 초과가 나는 것 같다.

 

 

 

그래서 최소한의 로직으로 배열로만 구현하니 통과했다. 아래는 소스 코드이다.

---

소스 코드

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