[알고리즘 풀이] LeetCode : Move Zeroes

문제

leetcode.com/explore/learn/card/fun-with-arrays/511/in-place-operations/3157/

Explore - LeetCode

Input: [0,1,0,3,12] Output: [1,3,12,0,0]

 

조건

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

---

문제해설

0이 무작위로 섞여있는 배열에서 0은 뒤로 몰아 빼는 문제이다.

중요한건 조건 1처럼 또 다른 배열을 만들어 결과로 반영시키면 안되고, 주어진 배열 그대로 그 배열을 변형시켜야 한다.

 

정답코드

nums = [0, 1, 0, 3, 12]
n = len(nums)
notZeroCount = 0
for i in range(n):
    if nums[i] != 0:
        nums[notZeroCount] = nums[i]
        notZeroCount += 1
while notZeroCount < n:
    nums[notZeroCount] = 0
    notZeroCount += 1
print(nums)	#[1, 3, 12, 0, 0]

가독성 좋게 임의의 예시를 적어두었다.

 

1. 우선 입력받은 배열의 길이를 n에 대입

2. 첫번째부터 0이 아닌 수로 채우기 위해 0이 아닌 수를 세기 위한 변수 notZeroCount 지정.

3. 받아온 배열을 처음부터 돌면서 해당 길이의 배열 요소가 0이 아니라면 처음부터 순서대로 숫자로 채운다.

4. 채워지면 다음 요소를 위해 notZeroCount에 1을 더한다.

5. for문이 끝나면 나머지 요소들을 0으로 채우기 위해 notZeroCount부터 처음에 받아온 배열의 길이까지 0으로 채운다.

 

---

간만에 깔끔하게 이해 한 문제다.

처음에 조건 1번 생각을 못하고 새로운 배열들을 만들어 코드를 짜고 nums에 복붙했는데 답이 안나왔다.

---

참고

www.geeksforgeeks.org/move-zeroes-end-array/