[투포인터][JavaScript][LeetCode] #977. Squares of a Sorted Array

#투포인터  #EASY

Squares of a Sorted Array - LeetCode

🌷 문제 설명

✏️ LeetCode 연습문제: Squares of a Sorted Array
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

🎃 제한 사항
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums is sorted in non-decreasing order

입출력 예

nums	result
[-4, -1, 0, 3, 10]	[0, 1, 9, 16, 100]
[-7, -3, 2, 3, 11]	[4, 9, 9, 49, 121]

 

🌷 내 코드

1. 투포인터

투포인터 쓰면 메모리도 덜 써야 되는거 아니여? 빠르면 장땡인가

var sortedSquares = function (nums) {
  let start = 0; // Pointer1
  let end = nums.length - 1; // Pointer2
  let idx = nums.length - 1; // answer 배열의 인덱스 역할을 할 것
  const answer = [];

  // answer index가 끝에서 0에 도달할 때 까지
  while (idx > -1) {
    // 절대값 비교시 왼쪽이 작으면,
    if (Math.abs(nums[start]) < Math.abs(nums[end])) {
      // 오른쪽 값을 answer 배열 오른쪽에 넣기 (desc order)
      answer[idx] = Math.pow(nums[end], 2);
      // 넣은 애는 이제 끝. 작은애(왼쪽)로 옮겨가자
      end--;
    } else {
      // 절대값 비교시 왼쪽이 크면, 왼쪽 값을 answer 배열 오른쪽에 넣기
      answer[idx] = Math.pow(nums[start], 2);
      // 넣은 애는 이제 끝. 큰 애(오른쪽)로 옮겨가자
      start++;
    }
    // loop 하나 돌 때마다 idx 하나씩 차감
    idx--;
  }
  return answer;
};

2. 무지성 forEach

이제 약간 내가 왜 코테 광탈했는지 알거같당ㅎㅎ 무지성으로 포문을 돌리는 나.. 그리고 투포인터 쓰는 대다수

var sortedSquares = function(nums) {
    const answer = []
    nums.forEach((n) => {
        answer.push(Math.pow(n, 2))
    })
    return answer.sort((a,b)=>a-b)
};

2. 쪼오금 생각을 했을 때 (map)

오 그래도 꽤 괜찮은데? 하지만 투포인터 연습문제에 투포인터가 아니면 무슨 의미가 있겠어요;

var sortedSquares = function(nums) {
    return nums.map((n)=>n*n).sort((a,b)=>a-b)
}

 

🌷 코멘트

👉 포인트는 'sort()' 메서드 안 쓰는 것! => sort()의 시간복잡도는 O(N log N)
👉 투포인터 첨엔 주석넣고 돌렸을 때 82ms 나왔는데, 메모리가 좀 크게 나와서 혹시 주석 때문에 그런가...? 싶어서 주석만 싹 빼고 다시 돌려봤더니 메모리 0.3mb작아지고 110ms 나온거 실화..?(심지어 forEach, sort조합보다 느림;) 어쩌란거지? 오늘도 알수 없는 코딩의 세계,,, 문과는 자러갑니다

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!

~대가리 꽃밭인 디지털 노마드가 꿈이예요~

🧚‍♀️ Gyumin Lee

📧 gyumin.q.lee@gmail.com

qminlee723 - Overview