알고리즘 공부 Leetcode Day4
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.
금일 문제는 각 배열에 제곱근을 한 뒤 재배열을 하는 문제이다. 필자는 처음에
import java.util.Arrays;
class Solution {
public int[] sortedSquares(int[] nums) {
int[] result =new int[nums.length];
for(int i=0;i<nums.length;i++){
int temp=nums[i]*nums[i];
result[i]=temp;
}
Arrays.sort(result);
return result;
}
}
패키지 Arrays를 생각하였고 반복문에서 각 제곱근을 구한뒤 배열에 넣고 마지막 단계에서 정렬을 해주었다.
하지만 이 방법은 패키지를 사용하였다는 점에서 이 문제에서 원하는 알고리즘을 푼 것이 아니라고 생각하였다. 따라서 이 문제에 접근을 다시 생각하였다.
이 문제에서는 이미 오름차순으로 배열이 넘어온 상태이다.이를 활용하여 첫번쨰와 마지막 제곱근을 비교하면 정렬이 가능하다 만약 오른쪽(end값) 이 크다 가정하면 e값을 줄이면 된다 반대로 왼쪽값(start)값이 크면 그 값을 출력배열에 넣고 배열위치를 뺴고 start 위치는 증가시키면 해결 할 수 있다. 판단되었다
class Solution {
public int[] sortedSquares(int[] nums) {
int start = 0;
int end = nums.length-1;
int[] result = new int[nums.length];
int temp = nums.length-1;
while(start<=end){
if(nums[start]*nums[start] < nums[end]*nums[end]){
result[temp] = nums[end]*nums[end];
temp--;
end--;
}else{
result[temp] = nums[start]*nums[start];
temp--;
start++;
}
}
return result;
}
}
Input nums[-4,-1,0,3,10] Ouput [0 ,1 , 9, 16, 100]
| TestCase | start | end | temp | nums[start],nums[end] | result[temp] |
| 1 | 0 | 4 | 4 | 16 < 100 | result[4]=100 |
| 2 | 0 | 3 | 3 | 16 >9 | result[3]=16 |
| 3 | 1 | 3 | 2 | 1 <9 | result[2]=9 |
| 4 | 1 | 2 | 1 | 1 > 0 | result[1]=1 |
| 5 | 2 | 2 | 0 | 0 =0 | result[0]=0 |
| 6 | 3 | 2 | 에 따른 와일문 조건 | False로 빠져나감 |
처음에는 패키지로 생각하여서 문제 방향이 완전히 달랐다 또한 맨처음 패키지 사용과 알고리즘 방식으로하였을때 Runtime시간도많이 차이가 났다.
결과적으로 실행이 되면 좋겠지만 좋은 개발자 , 효율적인 개발자가 되기위해서는 결과적으로 시간을 줄이고 용량이 적은 코드가 더 좋을 것이다. 그러기 위해서는 처음보는 알고리즘이라도 모르면 찾아보고 그 개념을 천천히 적용시키고 테스트케이스로 스스로 디버깅도 하면서 늘리면 될거라 생각된다.