2149. Rearrange Array Elements by Sign

[zeikar]

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