[C++] LeetCode - 283 : Move Zeroes

14 Apr 2024 in Develop on C++, Algorithm

• 문제
• 예시
• 제한 조건
• 알고리즘
• 풀이
• 코드
• 평가

문제

LeetCode - 283 : Move Zeroes(링크)

Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

예시

Example 1:

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

Example 2:

Input: nums = [0]
Output: [0]

제한 조건

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

알고리즘

1. 정렬
2. 투포인터 알고리즘

풀이

• 0은 무시하고 0이 아닌 숫자를 땡겨서 위치시킨다
• 정적 배열의 용량이 미리 정해져 있다는 특성을 이용
• 증가한 j값 만큼 nums[i]에 0을 추가해준다

코드

// LeetCode - 283 : Move Zeroes
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int j= 0;
        for(int i = 0; i< nums.size(); i++)
        {
            if(nums[i] != 0)
            {
                nums[j] = nums[i];
                j++;
            }
        }
        for(int i= j; i < nums.size(); i++)
        {
            nums[i] = 0;
        }
    }
};

평가

• In-place Algorithm
  • 자료구조를 추가로 사용하지 않고 입력을 변호나하는 알고리즘
  • 자료구조에는 배열, 객체, 스택 등이 있다
  • 요소를 교체하기 위한 O(1)의 추가적인 저장 공간만 필요하다
  • 버블 정렬, 빗 정렬, 선택 정렬, 삽입 정렬, 힙정렬, 셀 정렬 등