Problem link
https://leetcode.com/problems/rearrange-array-elements-by-sign
Problem Summary
배열이 있을 때 양수 음수가 번갈아 나오게 하면서 양수 음수의 순서를 유지한 채로 재정렬하는 문제.
Solution
너무 쉽다... 일단 처음 풀이는 양수와 음수 배열을 각각 선언 후 하나씩 빼서 최종 배열을 만들었는데 O(2n). 이것보다 더 줄일 수 있다.
일종의 투 포인터로 양수와 음수가 나올 때마다 정답 배열에 끼워넣는 방식으로 넣어주면 된다. O(n)
Source Code
class Solution:
def rearrangeArray(self, nums: List[int]) -> List[int]:
pos_idx, neg_idx = 0, 0
res = [0] * len(nums)
for num in nums:
if num < 0:
res[neg_idx * 2 + 1] = num
neg_idx += 1
else:
res[pos_idx * 2] = num
pos_idx += 1
return res