.leetcode(977. Squares of a Sorted Array)

https://leetcode.com/problems/squares-of-a-sorted-array/

 

 

3. 2022/04/28 시도

소요시간: 4분

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        
        int index = nums.length - 1;
        int[] ret = new int[nums.length];
        while (left <= right) {
            int lv = nums[left] * nums[left];
            int rv = nums[right] * nums[right];
            
            if (lv < rv) {
                ret[index--] = rv;
                right--;
            } else {
                ret[index--] = lv;
                left++;
            }
        }
        
        return ret;
    }
}

풀이 접근 과정

이미 정렬되어있기에 left, right 인덱스를 이용해서 비교해본다. 

 

느낀점

• 푼지 얼마 안되고 다시 풀어서 금방 풀 수 있었다.

---

 

2. 2022.04.16 시도

소요시간: 9분

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        
        int[] newone = new int[nums.length];
        int index = nums.length-1;
        
        while (left <= right) {
            int ln = Math.abs(nums[left]);
            int rn = Math.abs(nums[right]);
            
            if (ln < rn) {
                newone[index--] = rn*rn;
                right--;
            } else {
                newone[index--] = ln*ln;
                left++;
            }
        }
        
        return newone;
    }
}

풀이 접근 과정

정렬이 되어있다는게 포인트다. 문제에 주어진 특성을 이용해보면 음수와 정수는 각각 특정 지점을 기준으로 정렬이 되어있다.

절대값으로 볼 때는 음수, 양수의 양끝에는 가장 큰수를 갖기 마련이다.

따라서 양쪽에서 한쪽씩 포인터로 확인하면서 새로운 배열을 완성해주는 방식으로 풀었다.

 

느낀점

• 배열 문제는 left, right 인덱스를 한번씩 생각해볼 만하다. 이번에도 그렇게 생각해서 접근하니 금방 풀렸다.

---

1. 2022.01.30 시도

소요시간: 12분(구상 4분, 풀이 8분)

// O(n)
class Solution {
    public int[] sortedSquares(int[] nums) {
        if (nums == null) {
            return nums;
        }
        
        // find zero
        int right = 0;
        for (int num: nums) {
            if (num >=0) {
                break;
            }
            
            right++;
        }
        int left = right-1;
        
        // add one by one
        int[] ret = new int[nums.length];
        int pointer = 0;
        while(pointer < nums.length) {
            if (left <= -1) {
                ret[pointer++] = nums[right] * nums[right];
                right++;
            } else if (right >= nums.length) {
                ret[pointer++] = nums[left] * nums[left];
                left--;
            } else {
                if (nums[left]* -1 <= nums[right]) {
                    ret[pointer++] = nums[left] * nums[left];
                    left--;
                } else {
                    ret[pointer++] = nums[right] * nums[right];
                    right++;
                }
            }
        }
        
        return ret;
    }
}

풀이 접근 과정

이런 정렬된 배열이 나오면 항상 포인터를 염두해 둘 필요가 있다.
O(n)으로 풀어보기 위해서 먼저 생각이 든건 -+의 구분이다. 0>= 지점을 찾아낸다. 그 후에  포인터 2개를 두고 절대값을 비교하여 left -- , right++해서 출력할 배열을 만들어간다.

 

느낀점

• 포인터로 접근하니 문제가 잘 풀렸다. 
• 나는 작은거부터 배열해서 넣었는데 사실 큰거 부터 체크해서 배열 뒤에서 넣어도 상관없겠다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형