[LeetCode] 977. Squares of a Sorted Array, Easy

2025. 3. 4. 18:22·CodingTest/LeetCode
반응형

1. 문제

  • 오름차순으로 정렬된 배열이 주어질 때, 각 요소를 제곱한 뒤에도 오름차순을 유지하는 배열을 반환하라.

2. 해결

function sortedSquares(nums: number[]): number[] {
    const result = nums.map(num => Math.pow(num, 2))
        
    result.sort((a,b) => a-b);
    
    return result;
};
  • 우선, 문제를 보자마자 떠올린 방법이다. 단순히 모든 배열을 순환하며 제곱하고, 해당 배열을 정렬한다.
  • 이 경우, O(NlogN) 시간 복잡도가 나온다.
function sortedSquares(nums: number[]): number[] {
    const result = new Array(nums.length) // 1. 결과를 담을 배열.
    let left = 0, right = nums.length -1, index = nums.length -1; // 각 포인터 및 인덱스.

    while(left <= right) { // 2. 두 포인터가 만날 때 까지 반복.
        const leftVal = Math.pow(nums[left],2);
        const rightVal = Math.pow(nums[right],2);
		
        // 3. 두 포인터의 제곱값 중 큰 값을 현재 인덱스에 넣고 포인터 조정.
        if(rightVal >= leftVal) {   
            result[index] = rightVal;
            right-=1;
        } else {
            result[index] = leftVal;
            left+=1;
        }

        index--;
    }

    return result;
};
  • 다른 사람들의 풀이 방법 중, 투 포인터를 이용한 방법이 있길래 사용해봤다.
  • 원리는, 배열의 시작과 끝에 포인터를 두고 두 포인터가 만날 때 까지 각 포인터의 제곱값을 비교하여 마지막 요소부터 채우는 것.
  • 내가 첫 번째 방법으로 생각한 이유는? 
    • -121, 1, 2 ,11 다음과 같이 오름차순 배열이 주어지면, -121의 제곱값이 가장 크므로 맨 뒤에 위치해야 한다.
    • 그러니깐, 제곱하고 다시 정렬을 해줘야 겠구나.
  • 근데 두 번째 방법이 가능한 이유는?
    • 애초에 오름차순 정렬된 배열이 주어지기 때문.
    • 결과 배열의 마지막 요소가 바뀔 가능성은? 첫 번째 요소부터 제곱값이 큰 경우.
    • 그럼 첫 번째 요소부터 제곱값을 비교해가며 값을 채운다.

Reference

  • https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Algorithm/%ED%88%AC%ED%8F%AC%EC%9D%B8%ED%84%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.md
 

Ready-For-Tech-Interview/Algorithm/투포인터 알고리즘.md at master · WooVictory/Ready-For-Tech-Interview

💻 신입 개발자로서 지식을 쌓기 위해 공부하는 공간 👨‍💻. Contribute to WooVictory/Ready-For-Tech-Interview development by creating an account on GitHub.

github.com

 

저작자표시 (새창열림)
'CodingTest/LeetCode' 카테고리의 다른 글
  • [LeetCode] 88. Merge Sorted Array, Easy
  • [LeetCode] 1089. Duplicate Zeros, Easy
  • [LeetCode] 1295. Find Numbers with Even Number of Digits, Easy
  • [LeetCode] 485. Max Consecutive Ones, Easy
뜸부깅
뜸부깅
코딩에 대한 여러 개인적인 생각을 정리하고 공부를 하는 공간입니다!!
  • 뜸부깅
    코오오딩
    뜸부깅
  • 전체
    오늘
    어제
    • Note (429)
      • Skill (31)
        • Java & Spring (9)
        • Javascript & HTML & CSS (0)
        • React (0)
        • Next.js (22)
      • CodingTest (389)
        • 백준 온라인 저지(BOJ) (140)
        • 프로그래머스(Programmers) (79)
        • LeetCode (170)
      • Algorithm & Data Structure (6)
      • [Project] 포트폴리오 (3)
        • Front end (3)
        • Back end (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    Java
    boj2108
    boj1427
    Easy
    프로그래머스
    자바
    알고리즘
    medium
    BOJ
    백준2751
    meidum
    백준1260
    next 14
    백준
    백준1427
    TypeScript
    백준7576자바
    component-scan
    leetcode 2236
    백준7576
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
뜸부깅
[LeetCode] 977. Squares of a Sorted Array, Easy
상단으로

티스토리툴바