LeetCode의 Move Zeroes 문제를 함께 풀어보도록 하겠습니다.
문제
정수의 배열 nums가 주어졌을 때, 배열 내에 있는 모든 0을 맨 뒤로 옮겨라.
단, 0이 아닌 원소들의 순서가 배열 내에서 그대로 유지되어야 한다.
(작성할 함수는 아무 것도 반환하지 않고 주어진 배열의 원소들의 위치만 변경해야 함)
예제
- 입력
[0, 1, 0, 3, 2]- 결과
[1, 3, 2, 0, 0]풀이 1
주어진 예제를 통해서 이 문제를 어떻게 풀 수 있을지 생각해보겠습니다.
0, 1, 0, 3, 2
👆우선, 첫 번째 원소는 0이기 때문에 배열에 맨 앞에 있으면 안 되겠죠?
이 0을 뒤로 옮겨야할텐데 어느 위치로 보내야할까요?
👇
0, 1, 0, 3, 2
👆0 우측에 있는 원소 중에서 가장 왼쪽에 있는 0이 아닌 원소와 자리를 바꿔야할 것 입니다.
0이 아닌 원소들의 순서가 배열 내에서 그대로 유지되어야 하기 때문이지요.
따라서 첫 번째 원소인 0과 두 번째 원소인 1의 자리를 바꾸도록 하겠습니다.
1, 0, 0, 3, 2
👆이제 배열의 맨 앞에 0이 아닌 숫자가 있기 때문에 다음 원소로 넘어가도 될 것 같습니다.
1, 0, 0, 3, 2
👆마찬가지로 여기는 0이 있으면 안 되는 자리입니다.
뒤에서 0이 아닌 첫 번째 원소는 어디에 있을까요?
👇
1, 0, 0, 3, 2
👆네, 3이 가장 왼쪽에 있는 0이 아닌 원소는 3 입니다.
따라서 첫 번째원소인 0과 네 번째 원소인 3의 자리를 바꾸겠습니다.
1, 3, 0, 0, 2
👆이제 배열의 첫 번째 원소와 두 번째 원소가 0이 아닌 숫자로 채워져 있으니 다음 원소로 넘어가겠습니다.
👇
1, 3, 0, 0, 2
👆마찬가지 과정을 반복하면 세 번째 원소인 0과 마지막 원소인 2의 자리를 바꿔야 한다는 것을 알 수 있습니다.
1, 3, 2, 0, 0
👆다음 원소로 넘어갔더니 더 이상 우측에 0이 아닌 원소가 발견되지 않아서 더 이상 자리를 바꿀 필요가 없네요.
1, 3, 2, 0, 0
👆이렇게 최종적으로 우리가 원하는대로 배열의 모습을 얻게 되었습니다.
그럼, 이 알고리즘을 그대로 코드로 한번 구현해볼까요?
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
for i in range(len(nums)):
if nums[i] == 0:
for j in range(i + 1, len(nums)):
if nums[j] != 0:
nums[i], nums[j] = nums[j], nums[i]
breakn을 주어진 배열의 크기라고 했을 때, 이 풀이의 시간 복잡도는 이중 루프로 인해서 O(n^2)이 됩니다.
배열 내에 0이 많으면 많을 수록 내부 반복문이 실행되는 회수가 커져서 이 코드는 비효율적으로 동작할 것입니다.
반면에 이 풀이의 공간 복잡도는 고정된 개수의 변수 i, j만을 사용하고 있기 때문에 O(1)입니다.
풀이 2
공간 복잡도를 조금 희생해서 시간 복잡도를 개선시킬 수 있는 경우가 많은데요. 이번에는 추가적인 메모리를 써서 실행 시간을 단축시킬 수 있는 방법을 한 번 생각해보면 어떨까요?
배열 내에 있는 모든 0을 맨 뒤로 옮긴다는 것은, 다르게 생각하면 0이 아닌 원소들을 맨 앞으로 옮긴다는 말과 같습니다.
결국 주어진 배열을 0인 원소들과, 0인 아닌 원소들 이렇게 2개로 쪼갠 후에 다시 합치면 원하는 모습의 배열을 얻을 수 있을 것입니다.
예제로 주어진 배열을 이 기준으로 한번 2개의 작은 배열로 나눠보겠습니다.
[0, 1, 0, 3, 2] 👉 [0, 0] + [1, 3, 2]이제 0인 아닌 원소를 담고 있는 배열을 앞에, 0인 원소를 담고 있는 배열을 뒤에 배치한 후, 두 배열을 연결합니다.
[1, 3, 2] + [0, 0] 👉 [1, 3, 2, 0, 0]이제 이 배열 내의 원소들을 주어진 배열로 복사하기만 하면 되겠죠? (이 문제는 새로운 배열을 대신에 주어진 배열을 변경하길 원한다는 것을 까먹지 않으셨죠?)
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
zeros = []
non_zeros = []
for num in nums:
if num == 0:
zeros.append(num)
else:
non_zeros.append(num)
nums[:] = non_zeros + zeros이 풀이의 시간 복잡도와 공간 복잡도는 모두 O(n) 입니다.
주어진 배열을 딱 한 번 루프를 돌며, 입력 배열의 크기와 동일한 추가적인 배열을 사용하기 때문입니다.
풀이 3
추가적인 배열을 사용하지 않고 이 문제를 풀 수는 없을까요?
그럴 수 있다면 공간 복잡도를 O(1)로 향상시킬 수 있을 겁니다!
배열과 관련된 코딩 문제를 풀 때 자주 쓰는 테크닉인 두 개의 포인터를 이용해보면 어떨까요?
먼저, 첫 번째 포인터(토끼)와 두 번째 포인터(거북이)를 배열의 맨 처음에 놓습니다.
🐇
0, 1, 0, 3, 2
🐢지금부터 토끼와 거북이를 우측으로 계속해서 이동시킬 것인데요.
토끼는 계속해서 0이 아닌 원소를 찾아서 이동하고, 거북이 포인터는 계속해서 0인 원소를 찾아서 이동합니다.
거북이는 이미 0인 원소에 있으므로, 토끼만 0이 아닌 원소로 이동시키겠습니다.
🐇
0, 1, 0, 3, 2
🐢이제 이 둘이 가리키고 있는 숫자의 자리를 바꿔줍니다.
🐇
1, 0, 0, 3, 2
🐢토끼는 0이 아닌 다음 원소를 찾으러 떠나고, 거북이는 0인 다음 원소를 찾으러 떠납니다.
🐇
1, 0, 0, 3, 2
🐢또 이 둘이 가리키고 있는 숫자의 자리를 바꿉니다.
🐇
1, 3, 0, 0, 2
🐢토끼와 거북이는 각각 0이 아닌 다음 원소와 0인 다음 원소를 찾으러 또 떠납니다.
🐇
1, 3, 0, 0, 2
🐢둘이 가리키고 있는 숫자의 자리를 또 바꿔줍니다.
🐇
1, 3, 2, 0, 0
🐢토끼가 먼저 배열의 끝에 도착했네요. 우리가 원했던 배열의 모습을 얻게 되었습니다.
🐇
1, 3, 2, 0, 0
🐢위 알고리즘을 정리해보겠습니다.
- 첫 번째 포인터(토끼)는 다음에 나오는
0이 아닌 원소로 이동 - 두 번째 포인터(거북이)는 다음에 나오는
0인 원소로 이동 - 이 둘이 기리키고 있는 숫자의 자리를 바꿈
- 위 세단계의 과정을 첫 번째 포인터가 배열의 끝에 다다를 떄까지 반복
정리한 알고리즘을 코드로 구현을 해볼까요?
lo가 거북이를 가리키는 포인터이고, hi가 토끼를 가리키는 포인터입니다.
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
lo, hi = 0, 0
while hi < len(nums):
if nums[hi] == 0:
hi += 1
else:
nums[lo], nums[hi] = nums[hi], nums[lo]
lo, hi = lo + 1, hi + 1while 루프 대신에 for 루프를 사용하니 코드가 좀 더 깔끔해지네요?
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
lo = 0
for hi in range(len(nums)):
if nums[hi] != 0:
nums[lo], nums[hi] = nums[hi], nums[lo]
lo += 1이 풀이의 시간 복잡도는 입력 배열을 단 한 번 루프를 돌기 때문에 O(n) 입니다.
lo와 hi 외에는 추가적인 추가적인 메모리를 사용하지 않기 때문에 공간 복잡도는 O(1) 입니다.
마치면서
쉽다고 생각할 수도 있지만 고민을해보면 다양한 방법으로 풀 수 있는 문제였습니다. 실제 코딩 인터뷰에서는 면접관과 토론을 하기에 적합한 종류의 문제라고 할 수 있겠습니다.