•
문제 설명 : 제공된 숫자들의 제곱 값을 오름차순으로 반환한다.
•
풀이 방법
◦
우선 sorted 를 사용하여 풀어보았다.
◦
다만 이 방법은 투포인터를 활용한 최선의 방법이 아니었다.
•
시간복잡도 :
•
성공 코드
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
return sorted([num ** 2 for num in nums])
Python
복사
•
개선 코드 (O(N))
이 코드의 핵심은 제곱 값의 크기는 연산에 사용되는 숫자의 절대 값에 영향을 받는다는 것이다.
양수, 음수가 섞여 있기 때문에 절대 값으로 따지면 음수가 양수보다 더 클 수도 있는 것이다.
따라서, 음수더라도 절대 값이 양수보다 크다면 제곱 연산 결과가 더 높은 인덱스에 존재해야한다.
그렇기 때문에 음수가 있는 초반 인덱스에 포인터를 설정하고, 높은 값의 양수가 존재하는 마지막 인덱스쪽에 포인터를 설정하여 절대 값을 비교하여 반환에 필요한 데이터를 만든다.
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
left = 0
right = len(nums) - 1
result = []
# 절대 값이 더 큰 요소를 추가
# 오름차순으로 정렬된 배열의 양끝에서 움직이기 때문에, 음수/양수에서 절대 값이 가장 큰 요소부터 시작한다.
# 탐색하면서 절대 값이 점점 작아지는 순서이기 때문에, 큰 요소를 먼저 넣어줘야한다.
# 커서가 움직인다면, 해당 커서의 다음 요소는 이전 요소보다 반드시 절대값이 작기 때문이다.
while left <= right:
if abs(nums[left]) >= abs(nums[right]):
result.append(nums[left] ** 2)
left += 1
elif abs(nums[left]) < abs(nums[right]):
result.append(nums[right] ** 2)
right -= 1
# 오름차순이기 때문에 뒤집어서 반환
return result[::-1]
Python
복사