Javascript / Array.shift(), Array.pop()

 

오늘은 지난 Queue를 구현하면서 dequeue를 구현할 때 shift() 메소드를 사용하면 안되는 이유를 보려해요.

 

먼저 간단히 dequeue는 queue의 front를 제거하는 동작이며, shift는 javascript의 Array의 메소드 중 하나로 맨 앞의 요소를 제거해요.

 

dequeue는 O(1)의 속도를 가지지만 shift는 O(n)의 속도를 가지기 때문에 그렇죠!

shift가 O(n)을 갖는 이유는 array는 기본적으로 인덱스를 통해 접근이 가능하죠?! 그러면 맨 앞의 요소를 제거한다면, 뒤에 있는 모든 요소의 인덱스를 하나씩 땡겨주는 작업을 해야해요.

그래서 맨 앞의 요소를 제거하는 shift와 추가하는 unshift 모두 O(n)의 속도를 가져요!

 

그러면 다음 문제를 통해서 속도차이를 실감해볼까요?!

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

 

 

 

먼저 문제를 간단하게 소개하자면 앞에서부터 수의 차이를 비교하며

• "w" : 수에 1을 더한다.
• "s" : 수에 1을 뺀다.
• "d" : 수에 10을 더한다.
• "a" : 수에 10을 뺀다.

이 로직을 통해서 리스트를 문자열로 리턴해주는 문제입니다.

 

먼저 shift를 통해 구현해보며 아래와 같아요

 

 

const MAP = {
    '1' : 'w',
    '-1' : 's',
    '10' : 'd',
    '-10' : 'a'
}
function solution(numLog) {
    var answer = '';
    let val = numLog.shift();
    
    while(numLog.length){
        const val2 = numLog.shift();
        const diff = val2 - val;
        val = val2
        answer += MAP[String(diff)];
    }
    return answer;
}a

 

 

numLog를 반복문을 통해 shift로 하나씩 제거하면서 차이를 통해 문자열에 더해주죠!

문제 결과의 속도를 보면!!

 

 

이렇게 나오는걸 볼 수 있을거에요! 이것만보면 비효율적인가...? 할 수 있지만 pop을 통해 구현해보면 어떤 차이가 있는지 확실히 볼 수 있어요 ㅎㅎ

const MAP = {
    '1' : 'w',
    '-1' : 's',
    '10' : 'd',
    '-10' : 'a'
}
function solution(numLog) {
    var answer = '';
    numLog.reverse()
    let val = numLog.pop();

    while(numLog.length){
        const val2 = numLog.pop();
        const diff = val2 - val;
        val = val2
        answer += MAP[String(diff)];
    }
    return answer;
}

 

이번엔 pop을 하기위해서 먼저 reverse를 통해 배열을 뒤집고 시작했어요!

결과는 두둥 .... ! 최악인 경우는 거의 50배까지 ;;; 속도차이가 있는걸 볼 수 있어요.

이 문제는 최대 길이가 10만이라서 그렇지만 실제로 테스트한 결과로는 50만의 길이로도 시간초과가 돼요!! 그렇기때문에 길이가 길어질수록 최악으로 됩니당ㅠㅠ

반대로 pop을 이용한 방법으로 했을 경우엔 길이가 1000만도 거뜬해요.

1번 방법은 O(n)의 속도 / 2번 방법은 O(n**2) 이기 때문에 나는 차이입니당

 

그렇기때문에 shift()는 길이가 긴 경우엔 안쓰는게 좋다는거!!!

끝!!!