[leetcode] 283. Move zeroes - C

문제

https://leetcode.com/problems/move-zeroes/

Move Zeroes - LeetCode

• 분류 - ?
• 난이도 - Easy
• 제약조건 
  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

 

 

---

문제 설명

수열 nums가 주어질 때, nums에 존재하는 0을 모두 가장 오른쪽으로 옮기는 문제

---

주의사항

배열을 복사하지 말고, 배열 내에서 요소의 위치를 바꾸어야 한다.

---

답안 코드 1 - 브루트포스

접근 방법

1) 배열의 맨뒤에서부터 탐색하여

2) 0이 맨 뒤가 아닌 곳에서 발견되면

3) 0의 다음 요소와 0의 자리를 바꾼다.

4) 1~3의 과정을 배열의 맨 앞에 도달할 때까지 반복한다.

 

제출 결과

Runtime: 345 ms, Memory Usage: 14.9 MB

int maxSubArray(int* nums, int numsSize){
    int sum=-10000;
    int max=-10000;
    
    for(int i=0; i<numsSize; i++){
        sum = 0;
        for(int j=i; j<numsSize; j++){
            sum += nums[j];
            if(max < sum){
                max = sum;
            }
        }
    }
    
    return max;
}

---

더 빠른 코드 - leetcode

접근 방법

1) 배열의 첫 요소부터 탐색하여 0의 자리에 0이 아닌 그 다음 요소를 당겨 채운다.

2) 0의 개수만큼 빈 뒷칸들에 0을 채운다.

코드 및 실행 결과

Runtime: 92 ms (100~80%) , Memory Usage: 15 MB (80.09%)

void moveZeroes(int* nums, int numsSize)
{
    int start = 0;
    for(int i = 0; i < numsSize; i++) {
        if(nums[i]) nums[start++] = nums[i];
    }
    
     while(start < numsSize) nums[start++] = 0;
}