[Leetcode/TwoPointer+Queue (Greedy)] 2149. Rearrange Array Elements by Sign

첫번째 방법 (Two-Pointer + Queue = Greedy)

(1) Two-Pointer 

• 두 개의 리스트 (positives, negatives)를 따로 저장한 후, 두 개의 포인터를 이용하여 한 번에 두 리스트를 합치는 방식 차용.
• 여기서 zip(positives, negatives)를 사용하여 두 리스트를 같은 인덱스에서 번갈아가며 가져오는 방식을 적용.

(2) Queue 

• Python의 리스트 (list)를 Queue처럼 사용하여 양수와 음수를 저장했다가 순차적으로 가져와서 최종 리스트를 생성하는 방식.
• positives.append(num) 및 negatives.append(num) 연산은 O(1) 이므로 효율적임.

• 여기서 zip(positives, negatives)를 사용하여 두 리스트를 같은 인덱스에서 번갈아가며 가져오는 방식을 적용.

(3) Greedy Algorithm 

• 각 단계에서 가장 최선의 선택 (양수와 음수를 번갈아가며 배치) 을 하여 최종적으로 문제의 조건을 만족하는 배열을 만든다.
• 미래의 경우를 고려할 필요 없이, 현재 양수와 음수를 순서대로 배치하는 것이 최적의 선택이므로 탐욕적 접근법이 적용된다.

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        positives = []
        negatives = []

        # 양수와 음수를 따로 저장
        for num in nums:
            if num > 0:
                positives.append(num)
            else:
                negatives.append(num)

        # 번갈아가면서 결과 리스트에 추가
        result = []
        for p, n in zip(positives, negatives):
            result.append(p)
            result.append(n)

        return result

📌 시간 복잡도 분석:

• nums를 한 번 순회하면서 양수와 음수를 분리 → O(n)
• positives와 negatives를 순회하면서 새로운 배열을 구성 → O(n)
• 전체 시간 복잡도는 O(n)

---

두번째 방법 (Two-Pointer)

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n  # 결과 리스트를 미리 0으로 초기화

        pos_idx, neg_idx = 0, 1  # 양수는 짝수 인덱스, 음수는 홀수 인덱스에 배치

        for num in nums:
            if num > 0:
                res[pos_idx] = num
                pos_idx += 2  # 다음 양수 위치
            else:
                res[neg_idx] = num
                neg_idx += 2  # 다음 음수 위치
        
        return res

문제 이해

• 주어진 nums 리스트에는 양수와 음수가 같은 개수 존재한다고 가정.
• 양수와 음수를 번갈아 가면서 배치해야 함

📌 시간 복잡도 분석

• nums를 한 번 순회하면서 res에 값을 채우므로 O(N).
• res 리스트를 미리 크기 n으로 초기화했기 때문에 추가적인 리스트 연산이 없음.
• 따라서 시간 복잡도: O(N), 공간 복잡도: O(N).

 

https://leetcode.com/problems/rearrange-array-elements-by-sign/description/