Squares of a Sorted Array
비내림차순으로 정렬된 정수 배열 nums가 주어집니다. 배열에는 음수 값이 포함될 수 있습니다. 모든 값을 제곱한 다음, 제곱한 값들을 비내림차순으로 정렬한 새 배열로 반환하세요.
함수
- numsinteger-array
- 음수가 허용되는 정수 정렬 배열
- 반환값integer-array
- 모든 값의 제곱을 비내림차순으로 정렬한 것
제약 조건
1 ≤ nums.length ≤ 4000-104 ≤ nums[i] ≤ 104nums는 비내림차순으로 정렬되어 있습니다.
예제
- 입력
- nums = [-6, -2, 1, 3, 7]
- 출력
- [1, 4, 9, 36, 49]
- 설명
- 원래 순서의 제곱수는 36, 4, 1, 9, 49입니다. 음수 값 -6과 -2는 큰 제곱수를 만들기 때문에 정렬하면 36이 끝부분으로 이동합니다:
[1, 4, 9, 36, 49].
- 입력
- nums = [-9, -4, -1]
- 출력
- [1, 16, 81]
- 설명
- 모든 값이 음수이므로 제곱한 결과가 역순으로 나옵니다. 81, 16, 1은
[1, 16, 81]이 됩니다.
제출 시 숨은 테스트 +14개
후속 질문
제곱하고 정렬하는 데는 O(n log n)이 걸립니다. O(n)에 할 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
[-6, -2, 1, 3, 7]의 각 원소를 손으로 제곱하세요. 배열의 어느 부분이 순서를 잃으며, 그 이유는 무엇인가요?가장 큰 제곱은 항상
nums의 첫 번째 값이나 마지막 값에서 나옵니다. 이 두 값이 0에서 가장 멀리 떨어져 있기 때문입니다.양쪽 끝에 포인터를 하나씩 놓으세요. 두 제곱수를 비교하고, 더 큰 수를 결과의 뒤쪽에 쓴 다음 해당 포인터를 안쪽으로 이동하세요. 모든 위치가 채워질 때까지 반복하세요.
풀이
제곱하면 음이 아닌 값들의 순서는 유지되지만 음수들의 순서는 뒤집히므로, 제곱한 값들은 정렬되어 있지 않습니다. 다시 정렬하면 되지만, 주어진 순서는 무시하게 됩니다. 핵심은 가장 큰 제곱값은 항상 nums의 양 끝 중 한쪽에서 나온다는 점입니다. 양 끝의 값을 비교하고, 더 큰 제곱값을 결과의 맨 뒤에 놓은 다음 안쪽으로 이동하세요.
제곱한 다음 정렬
핵심 아이디어
각 값의 제곱으로 새 배열을 만든 다음 정렬하세요. 제곱은 음수가 될 수 없으며, 정렬하면 값이 어디에서 왔든 순서대로 배치됩니다.
[-6, -2, 1, 3, 7]의 제곱은 [36, 4, 1, 9, 49]이고, 정렬하면 [1, 4, 9, 36, 49]가 됩니다.
정렬에는 O(n log n)의 비용이 듭니다. 여기서는 충분히 빠르지만, 입력이 정렬되어 있지 않은 것처럼 처리합니다. 다음 방법은 정렬된 순서를 활용하며 한 번만 순회하면 됩니다.
알고리즘
nums의 각x에 대해x * x를 사용하여 배열을 만드세요.- 숫자가 오름차순이 되도록 정렬하세요.
- 반환하세요.
def sortedSquares(nums):
return sorted(x * x for x in nums)양쪽 끝에서 시작하는 두 포인터
핵심 아이디어
제곱값은 0으로부터의 거리를 제곱한 값이라고 생각하세요. 정렬된 배열에서 0으로부터 가장 멀리 떨어진 값은 양쪽 끝에 있습니다. 왼쪽에는 가장 작은 음수 값이, 오른쪽에는 가장 큰 양수 값이 있습니다. 따라서 가장 큰 제곱값은 nums[left]² 또는 nums[right]²이며, 그 사이의 값은 절대 아닙니다.
left를 0에, right를 n-1에 두고, 결과 배열의 마지막 위치부터 거꾸로 채우세요. 각 단계에서 양쪽 끝 값의 제곱을 비교하고, 더 큰 값을 현재 위치에 넣은 다음 해당 포인터를 안쪽으로 이동하세요. 포인터 사이에 남은 부분도 정렬된 배열이므로, 매 단계마다 같은 원리가 적용됩니다.
[-6, -2, 1, 3, 7]에서는 49가 36보다 크므로 마지막에 놓입니다. 다음으로 36이 9보다 크고, 9가 4보다 크며, 4가 1보다 크므로, 마지막 1은 0번 위치를 채웁니다. 결과는 [1, 4, 9, 36, 49]입니다. 각 값은 한 번씩 배치됩니다. 시간 복잡도는 O(n)이고, 결과 배열만 추가로 필요합니다.
알고리즘
- 길이가
n인 결과 배열을 만듭니다.left를 0으로,right를n-1로 설정합니다. pos위치를n-1부터 0까지 역순으로 이동합니다.nums[left]²와nums[right]²를 비교합니다.- 더 큰 제곱을
pos에 쓰고 해당 포인터를 안쪽으로 한 칸 이동합니다. - 결과를 반환합니다.
def sortedSquares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
# the largest square left is always at one of the two ends
for pos in range(n - 1, -1, -1):
left_sq = nums[left] * nums[left]
right_sq = nums[right] * nums[right]
if left_sq > right_sq:
result[pos] = left_sq
left += 1
else:
result[pos] = right_sq
right -= 1
return result
함정과 경계 사례
투 포인터 방식은 짧지만, 몇 가지 세부 사항 때문에 제대로 작동하지 않을 수 있습니다.
- 결과를 앞에서부터 채우기. 가장 작은 제곱값은 값이 0을 가로지르는 위치에 있으며, 그 위치는 중간 어디든 될 수 있습니다. 양 끝에서는 가장 큰 제곱값만 알 수 있습니다. 뒤에서부터 채우세요.
- 제곱값이나 절댓값이 아니라
nums[left]와nums[right]를 비교하기. -6은 3보다 작지만, 제곱하면 더 큽니다. left가right와 만날 때 멈추기. 두 포인터가 같아지면 값 하나가 아직 배치되지 않은 상태입니다. 결과의 모든 위치를 순회하거나left <= right를 사용하세요.- 입력값이 모두 음수이거나 모두 양수인 경우.
[-9, -4, -1]에서는 왼쪽 포인터가 모든 작업을 하고,[2, 5, 8]에서는 오른쪽 포인터가 모든 작업을 합니다. 어느 경우든 정렬된 결과를 반환해야 합니다. - JavaScript와 TypeScript에서는 비교 함수 없이
sort()를 호출하면 숫자를 텍스트로 정렬하므로,[1, 4, 36, 9]는[1, 36, 4, 9]가 됩니다.(a, b) => a - b를 전달하세요.
자주 묻는 질문4
정렬된 배열의 제곱의 시간 복잡도는 얼마인가요?
투 포인터 솔루션은 O(n) 시간에 실행됩니다. 각 값은 한 번씩 제곱되어 배치됩니다. 제곱한 다음 정렬하면 O(n log n)의 시간이 듭니다. 두 방법 모두 결과를 저장하기 위해 O(n)의 메모리를 사용합니다.
가장 큰 정사각형은 왜 양쪽 끝 중 하나에서 나올까요?
제곱은 0에서 멀어질수록 커집니다. 정렬된 배열에서 0보다 작은 값 중 0에서 가장 먼 값은 첫 번째 값이고, 0보다 큰 값 중 0에서 가장 먼 값은 마지막 값입니다. 그 사이의 모든 값은 둘 중 하나보다 0에 더 가까우므로, 그 제곱이 가장 클 수는 없습니다.
대신 앞에서부터 결과를 채울 수 있나요?
네, 하지만 먼저 이진 검색 등을 사용해 값이 0을 지나는 위치를 찾아야 합니다. 그런 다음 두 포인터가 그 지점에서 바깥쪽으로 이동합니다. 두 정렬된 목록을 병합하는 것처럼 음수는 오른쪽에서 왼쪽으로 읽고, 0 이상인 값은 왼쪽에서 오른쪽으로 읽습니다. 뒤에서부터 채우면 양 끝의 위치를 처음부터 알 수 있으므로 검색을 피할 수 있습니다.
정렬된 배열의 제곱은 병합 문제인가요?
겉보기와는 달리 그렇습니다. 음수 값의 제곱은 하나의 정렬된 목록을 이루고(오른쪽에서 왼쪽으로 읽음), 0 이상인 값의 제곱은 또 다른 목록을 이룹니다. 두 목록을 합치는 과정은 병합 정렬의 병합 단계이므로, 한 번의 선형 순회로 처리할 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def sortedSquares(nums):
# 여기에 코드를 작성하세요케이스 1
케이스 2
입력
nums = [-6, -2, 1, 3, 7]
기대값
[1, 4, 9, 36, 49]