[Kotlin] Leetcode 977. Squares of a Sorted Array

Problem

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

 

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

 

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in non-decreasing order.

Solution

import kotlin.math.*
class Solution {
    fun sortedSquares(nums: IntArray): IntArray {
        var minusPointer = -1
        var plusPointer = nums.size
        for(i in 0..nums.size-1)
        {
            if(nums[i] < 0)
            {
                minusPointer = i
            } else if(nums[i] >= 0)
            {
                plusPointer = i
                break
            }
        }
        var newNums = mutableListOf<Int>()
        var bool = true
        while(bool)
        {
            //plus가 array의 끝까지 도달한 경우 => minus를 0까지 전부 제곱해서 저장
            //minus가 array의 시작점까지 도달한 경우 => plus를 end까지 전부 제곱해서 저장
            if (plusPointer == nums.size)
            {
                for (j in minusPointer downTo 0)
                {
                    newNums.add(nums[j]*nums[j])
                }
                break
            } 
            else if(minusPointer == -1)
            {
                for (j in plusPointer..nums.size-1 )
                {
                    newNums.add(nums[j]*nums[j])
                }
                break
            }
            else if (plusPointer == minusPointer)
            {
                newNums.add(nums[plusPointer]*nums[plusPointer])
                break
            }
            //plus와 minus의 abs값이 작은 것을 먼저 newNums에 저장
            if(nums[plusPointer] > abs(nums[minusPointer]))
            {
                newNums.add(nums[minusPointer] * nums[minusPointer])
                minusPointer -= 1
            } 
            else {
                newNums.add(nums[plusPointer] * nums[plusPointer])
                plusPointer += 1
            }
        }
        return newNums.toIntArray()
    }
}

 

for문을 돌며 minusPointer와 plusPointer를 찾아서 둘중 절대 값이 작은 것을 새로운 배열에 넣고 plusPointer는 오른쪽 배열이 모두 +이므로 +1을 해주고 minusPointer는 왼쪽 배열이 모두 -이므로 -1을 해주면서 값을 update한다.

 

plusPointer가 배열에 끝에 도달하면 plus 값들은 끝났으므로 minusPointer에 있는 것을 모두 처리한다.

반대로 minsPointer가 -1에 도착하면 minus 값은 끝난 것이므로 plusPointer를 증가시켜 모두 처리하면 된다.

 

fun sortedSquares(nums: IntArray): IntArray {
        val sortedNums = Array(nums.size) { 0 }
        var leftPointer = 0
        var rightPointer = nums.lastIndex
        var currentIndex = nums.lastIndex
        while (rightPointer != leftPointer) {
            val left = nums[leftPointer] * nums[leftPointer]
            val right = nums[rightPointer] * nums[rightPointer]
            if (left > right) {
                sortedNums[currentIndex] = left
                leftPointer++
            } else {
                sortedNums[currentIndex] = right
                rightPointer--
            }
            currentIndex--
        }
        sortedNums[0] = nums[leftPointer] * nums[leftPointer]
        return sortedNums.toIntArray()
    }

이 코드도 비슷한 개념인데 leftPointer = 0, rightPointer를 num의 마지막 index로 설정하고 제곱 값이 큰 경우를 sortedNums의 마지막 index에 넣는다. (왼쪽끝, 오른쪽 끝에 있는 값 중에 제곱이 가장 큰 값이 sortedNums에서 가장 큰 값이 될 것이다!) 

 

nums = [-4, -1, 0, 3, 10] 이면 leftPointer의 값은 -4 rightPointer의 값은 10이 될텐데 각각 제곱하면 16, 100이된다.

이 두 값은 -와 +의 제곱 값 중 가장 큰 값이 된다. 그렇기 때문에 가장 큰 값을 sortedNums의 마지막 index에 넣어준다. 

 

left가 right보다 크면 leftPointer를 증가시켜주고 right가 더 크면 rightPointer를 감소시킨다.

그리고 sortedNums의 index를 감소시킨다.

rightPointer와 leftPointer가 같아지면 그 값의 제곱이 가장 작은 값이 될 것이므로 sortedNums[0] 에 넣어주면 된다.