dbstnsdl12   1년 전

입력 받는 방법도 바꿔보고 출력 구성방식도 길이 접근방식 다 바꿔봤는데도 계속 시간초과가 나는데 

이유를 전혀 모르겠어서 질문게시판에 몇 안되는 node.js 질문글을 보니 전부 다 Queue와 Node 클래스를 직접 구현한 코드더라구요

JS내장 배열을 사용하면 시간안에 풀수가 없는 문제인건가요?

wizardrabbit   1년 전

JavaScript의 내장 배열을 사용하고, 원소를 넣기 위해 $\mathrm{Array.prototype.unshift}$를 사용하는 경우에는 효율성으로 인해 문제가 될 수 있습니다. 이 메서드의 시간복잡도는 $O(N)$이기 때문입니다. 하나의 원소를 넣기 위해 나머지 원소들을 전부 오른쪽으로 옮긴 것과 같습니다. 첫 번째 원소를 빼내는 $\mathrm{Array.prototype.shift}$도 마찬가지입니다. 백준에 있는 "큐" 문제와 달리 이 문제는 입력 제한이 굉장히 크기 때문에 효율성이 좋아야 합니다.

이를 해결하기 위해 많은 JavaScript 사용자분들은 이러한 연산을 할 때 배열의 맨 앞에서 직접 원소를 추가하거나 제거하기보다는, 원소들이 있는 범위를 가리키는 변수값만 조절하는 방식으로 효율성이 나빠지는 것을 막습니다.

예를 들어 질문자님의 구현 방식과는 다르지만 원소를 넣을 때 $\mathrm{Array.prototype.push}$를 사용하고, 원소를 제거할 때 $\mathrm{Array.prototype.shift}$를 사용한다고 해 볼게요. 여기에서는 원소를 넣는 상황에서는 시간복잡도가 $O(1)$이므로 문제가 되지 않으나, 원소를 맨 앞에서 하나 제거하면 나머지 원소들이 모두 이동해야 하므로 $O(N)$이 되어 비효율적이니까, 맨 앞의 원소를 제거하는 대신, "큐의 맨 끝부분을 가리키는 변수" $\mathrm{index = 0}$를 두고, $\mathrm{index}$ 값을 $1$ 증가시켜 $\mathrm{index = 1}$로 두는 방식 등을 사용할 수 있습니다. $\mathrm{index = 1}$이므로 배열의 $0$번째 값은 제거된 셈 친 것이고, 이후 다시 큐에서 값을 받아올 때 $\mathrm{index}$ 값을 활용하여 받아올 수 있겠죠.

JavaScript의 표준 라이브러리에는 별도로 큐를 제공하지 않기에, 많은 분들이 각자의 방식으로 클래스를 별도로 만들어 사용합니다. 그러나 클래스가 꼭 필수인 것은 아니며, 앞서 말씀드린 효율성 문제만 해결된다면 클래스의 사용 여부는 크게 중요하지는 않습니다.

스터디를 운영할 때 이 내용을 다룬 적이 있었는데 이 자료도 한 번 올려볼게요.

Quest_Week2_큐_덱.pdf

dbstnsdl12   1년 전

친절하고 상세한 답변 감사드립니다.

저도 처음에는 push, shift를 사용해서 구현했다가 이리저리 만져보다가 바꿔봤었는데 결국은 방향을 어디로 하든 원소를 제거할때 비효율이라는 같은 문제가 있던 것이었군요.

답변을 확인하기 전에 몇번의 제출과 실패를 반복하고서 말씀하신 것처럼 index를 사용하는 방법으로 정답을 받았습니다.

배열이 비효율적이라면 객체라면 될까 싶어서 객체 리터럴을 사용했는데, delete 키워드를 사용해도 결국은 말씀해주신 것처럼 나머지 원소들에 대해 인덱스 재배열을 해줘야하는 비효율이 있어서 그부분을 처리하려다보니 투포인터처럼 되어버렸네요.

비어있음 체크 및 사이즈도 두 인덱스를 비교하는 처리로 가능해보여서 그렇게 처리해봤습니다.

실제로는 delete 키워드가 없어도 통과는 할것 같은데 메모리 측면에서는 유지하는것도 괜찮을 것 같네요.

다시한번 답변 감사드립니다.

댓글을 작성하려면 로그인해야 합니다.