Problem Solving/?

[leetcode] 283. Move zeroes - C

Dev_en 2022. 3. 12. 00:00

문제

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

 

Move Zeroes - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

  • 분류 - ?
  • 난이도 - 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;
}