본문으로 바로가기
쉬움

Squares of a Sorted Array

코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.

입력
1함수 정렬제곱(nums):2  결과 = 크기 n,  왼 = 0,  오 = n-13  반복 자리 = n-1 … 0:4    만약 |nums[왼]| > |nums[오]|:5      결과[자리] = nums[왼]²,  왼 += 16    아니면:7      결과[자리] = nums[오]²,  오 -= 18  반환 결과
변수
왼
0
오
4

1 / 7절댓값이 큰 쪽은 항상 양끝 중 하나입니다. 결과의 뒤부터 채웁니다.

제곱은 음수 쪽이 커질 수 있어 정렬이 깨진다 — 절댓값이 큰 양끝을 비교해 결과 뒤부터 채운다.

왜 헷갈리는가

그냥 '전부 제곱 후 정렬'하면 O(n log n)이다. 입력이 이미 정렬돼 있다는 사실과 '절댓값 최대는 항상 양끝'이라는 성질을 쓰면 O(n)에 끝난다 — 이 두 관찰을 놓치면 최적해가 안 보인다.

핵심 아이디어

정렬된 배열에서 제곱값이 가장 큰 원소는 항상 왼끝(가장 음수) 또는 오른끝(가장 양수)이다. 둘의 절댓값을 비교해 큰 쪽을 결과의 뒤에서부터 채운다.

복잡도

시간 O(n)·공간 O(n)(결과 배열). '제곱 후 정렬'(O(n log n))보다 빠르다.

실무에서 어디에 쓰나

'정렬된 두(또는 양끝) 흐름을 병합해 새 정렬 순서를 만드는' 투포인터 병합의 응용이다.

  • 정렬 병합: 두 정렬 스트림을 하나의 정렬 결과로 합치기(merge)
  • 거리/편차: 기준점에서의 절댓값 거리로 재정렬(중앙값 근처 정렬)
  • 신호: 대칭 변환 후 크기순 재배열
  • 투포인터 병합 패턴의 확장 사례

흔한 실수

앞에서부터 채우려다 꼬이기(큰 값부터 뒤에서 채워야 함). 입력이 정렬돼 있다는 전제를 안 쓰기.

기억할 것

  • 절댓값 최대는 항상 양끝.
  • 결과는 뒤부터 채운다.
  • 제곱후정렬 O(n log n) → O(n).
  • 투포인터 병합의 응용.
Squares of a Sorted Array | KIE