프로그래머스 Lv.1 | (스택/큐) 같은 숫자는 싫어 js

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12906?language=javascript 

 

 

풀이

방법 1) 슬라이딩 윈도우

슬라이딩 윈도우 방식으로 풀었다. 본인과 본인 앞자리를 비교하는 방식이다.

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

 

방법 2) stack

아니면 answer의 맨 마지막 값과 중복되지 않는 새로운 수를 만나면 배열에 push하는 방식으로 풀 수도 있다.

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

 

효율성에서 탈락한 풀이

테스트 케이스는 다 통과했는데 효율성에서 탈락...

• for문으로 i < arr.length - 1 까지 돌며 i+1과 현재 인덱스 같은지 비교하고, 만약 같다면 i+1을 계속 지워버려서 중복된 원소를 제거하는 컨셉이다.
• while문을 이용해 현재 index 바로 다음에 오는(i+1) 값이 같다면 splice로 계속 지워준다.
• 다만 최악의 상황에는 1,000,000 (백만)개의 배열이 모두 같은 숫자로 꽉 차있을 수 있다. 이때 splice로 백만번을 계속 지워야 하는데, splice는 일부를 추가하거나 지울때마다 인덱스를 다시 매겨서 시간복잡도 O(n)를 가진다.
• 하나 지울때마다 거의 백만번 인덱스를 재부여해야 하니 백만개 지우려면 이 코드의 시간복잡도는 O(백만 * 백만)이 된다....

function solution(arr) {
    let curr;
    for(let i = 0; i < arr.length - 1; i++) {
        curr = arr[i];
        while(curr === arr[i + 1]) {
            arr.splice(i + 1, 1);
        }
    }
    return arr;
}