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;
}