[LeetCode] 2149. Rearrange Array Elements by Sign

- Problem

2149. Rearrange Array Elements by Sign

주어진 배열을 +,-,+,-,... 순서로 재배치하는 문제이다.

- 내 풀이 1

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        plus_list = collections.deque([])
        minus_list = collections.deque([])
        answer = []
        
        for num in nums:
            if num > 0:
                plus_list.append(num)
            else:
                minus_list.append(num)
                
        while plus_list:
            answer.append(plus_list.popleft())
            answer.append(minus_list.popleft())
        
        return answer

풀이법은 쉽게 떠올랐으나 시간 복잡도와 공간 복잡도를 전혀 고려하지 않은 풀이이다.

- 결과

당연히 패스.
하지만, 시간 복잡도 O(n)을 만족하고, 배열을 여러 개 추가하는 방법이 아닌 더 나은 풀이가 뭐가 있을까 조금 더 고민해보았다.

문제의 요구 조건을 잘 살펴보면, plus, minus 정수의 개수는 같다.
그렇다면, 주어진 배열의 길이는 2n을 만족할 것이고, 0,2,4,... 양수 인덱스는 항상 짝수이고, 1,3,5,... 음수 인덱스는 항상 홀수일 것이다.

- 내 풀이 2

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        answer = [0] * len(nums)
        p, m = 0, 1
        
        for num in nums:
            if num > 0:
                answer[p] = num
                p += 2
            
            else:
                answer[m] = num
                m += 2
        
        return answer

- 결과

answer 배열 외에 추가적인 리스트를 선언하지 않으므로 메모리 사용을 줄일 수 있었다.
또한, for 문을 한 번 돌게 됨(?)으로 인해 시간 복잡도를 조금 더 줄여볼 수 있었다...?
okay 넘겨