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

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

프로그래머스

 

목차

• 문제
• 풀이
• 코드

문제

입력

arr - 숫자 0부터 9까지 중 하나의 원소로 이루어진 배열

 

출력

answer - arr에서 연속으로 나타나는 숫자를 제거하고 남은 원소를 담은 배열

 

제한사항

• 배열 arr의 크기 : 1,000,000 이하의 자연수
• 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

풀이

이 문제는 스택을 사용해서 스택 마지막에 있는 원소와 배열의 원소가 다르면 스택에 새로운 원소를 집어넣어서 푸는 문제이다. 코드는  명령형 프로그래밍 방법과 선언형 프로그래밍 방법으로 짤 수 있다.

 

먼저 명령형 프로그래밍은 결과 값인 stack 배열을 선언하고 for 문을 돌려서 stack의 마지막 값이 for문의 타켓 원소와 같지 않다면 스택에 타켓 원소를 push하면 된다.

 

선언형 프로그래밍은 배열의 프로토타입 메서드인 forEach나 reduce를 사용하여 윗줄과 그대로 짜면 된다.

javascript는 선언형 프로그래밍을 따르므로 아래의 방법으로 짜 볼 것이다.

 

reduce는 방법이 간단하나 시간초과가 뜬다.

arr.reduce((a, v) => a.at(-1)!==v ? [...a, v]  : a, []);

이 코드는 reduce 메서드와 확장 연산자를 사용하므로 훨씬 오래 걸린다.

(a.push(v)는 사용할 수 없다. 왜냐하면 reduce의 초깃값으로 작성한 []의 원시타입은 string이기 때문이다. 이와 마찬가지로 a.at(-1)를 사용하기 보다는 a[a.length-1]를 활용하는 것이 좋다. reduce의 작동 방식을 제대로 알 수 없어서 이것 저것 다 넣어봤다. 아마도 reduce는 기본적으로 문자열을 내 놓으려고 사용하는 메소드인 거 같다. 문자열을 더하는 경우가 가장 기본적이고 이게 아니라면 자동 형변환으로 숫자로 나오기도 한다.)

 

따라서 결과를 담는 배열을 선언하고 빈 배열을 할당한 후에 forEach 메소드를 사용하여 결과를 담는 배열의 마지막 원소와 현재 순회하고 있는 원소가 같지 않다면 결과를 담는 배열에 추가하도록 구현하였다.

이 때 단축 평가라는 방법으로 구현했다.

 

시간복잡도는 주어진 배열을 순회하는 데 걸리는 시간인 O(n)이다.

공간복잡도는 주어진 배열을 저장하고 결과를 담는 배열도 저장하므로 O(2n)이다.

코드

function solution(arr)
{
    answer = [];
    arr.forEach(v => answer.at(-1)!==v && answer.push(v));
    
    return answer;
}

 

reduce 좀 더 알아보자. 기능이 많은 메소드다.

단축 평가, 설명을 못하겠다. 다시 보자.