[2024] day 45. 2149. Rearrange Array Elements by Sign

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 2월 14일 (수)
Leetcode daily problem

2149. Rearrange Array Elements by Sign

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

Problem

동일한 수의 양수와 음수로 구성된 짝수 길이의 정수 배열 nums가 있을 때, 정수 배열을 아래의 조건에 따르도록 재배열한다.
[조건]

• 모든 연속된 정수 쌍은 반대 부호를 갖는다. (+,-,+,- ... )
• 동일한 부호를 가진 모든 정수의 경우 숫자로 표시된 순서가 유지된다.
• 양의 정수가 시작하는 배열로 재배열한다.

Solution

array

일단, 배열에 있는 원소들을 짝수, 홀수로 나눠서 새로운 리스트로 할당해서 재배열할 배열을 만들어서 순서대로 넣는 방법도 있다.
해당 방법은 시간복잡도, 공간복잡도가 O(n) 이다.

같은 시간복잡도 및 공간복잡도를 가지지만 짝수, 홀수 원소를 저장할 배열을 생성하지 않고 그냥 재배열할 배열만 생성한 후에, 양의 인덱스, 음의 포인터(인덱스)를 업데이트 해가면서 원소를 업데이트하는 방법도 있다.

양의 인덱스를 0, 음의 인덱스를 1로 초기화한다.
주어진 배열을 탐색하면서, 첫 번째 나온 원소가 양수라고 한다면 현재 0으로 초기화되어 있는 양의 인덱스의 자리에 재배열할 배열에 양수원소를 넣고 해당 인덱스에 +2를 더하고 업데이트한다. 다음으로 나올 양의 원소가 2번째 인덱스에 들어가도록 인덱스 포인터를 바꾼다.

만약 첫 번째 나온 원소가 음수라고 한다면, 음의 인덱스 자리에 해당 원소를 넣고 음의 인덱스에 +2를 넣어 3번째 인덱스에 들어가도록 하는 것이다.

이해하기 쉬운 leetcode solution 랭커의 그림

Code

class Solution:
    def firstPalindrome(self, words: List[str]) -> str:
        for word in words:
            left, right = 0, len(word)-1
            while left < right:
                if word[left] != word[right]:
                    break
                left +=1
                right -=1
            
            else:
                return word
        
        return ""
        

Complexicity

시간 복잡도

주어진 num 배열을 탐색하는데 nums의 크기 만큼 탐색하므로 시간복잡도는 O(n) 이다.

공간 복잡도

재배열할 배열을 n의 크기만큼 생성하므로 공간복잡도는 O(n)이다.

---