LeetCode 문제 중 난이도 Easy인 Move Zeroes이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.
문제해석
주어진 배열 nums의 모든 0 값들을 뒤쪽으로 이동시키면서 0이 아닌 값의 순서는 그대로 유지하는 함수를 작성해라.
* nums의 복사본인 새로운 배열을 생성하지 않고 nums배열에서 작업한다
* 전체 연산의 수를 최소화한다
첫번째 방법은 가장 처음으로 0이 나오는 값의 인덱스를 구한다. 그리고 0의 인덱스값 뒤에 오는 요소들 중 처음으로 나오는 0이 아닌 숫자를 0의 인덱스에 넣고 숫자가 있던 자리는 0으로 바꾼다. 배열의 값이 0인 인덱스들에 같은 행위를 반복한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | class Solution { public void moveZeroes(int[] nums) { int indexOfZero=-1; //맨처음 0을 찾아서 index값 가져옴 for(int i=0 ; i<nums.length ; i++){ if(nums[i]==0){ indexOfZero=i; break; } } //0이 없으면 그대로 리턴 if(indexOfZero==-1) return; //0이 있는곳으로 뒤에서 0이 아닌수를 가져오고 index를 하나 늘린다(반복) for(int i=zeroIndex ; i<nums.length ; i++){ if(nums[i]==0) continue; nums[indexOfZero]=nums[i]; nums[i]=0; indexOfZero++; } } } | cs |
시간복잡도는 O(n), 공간복잡도는 O(1)이다. 이 방법은 경우에 따라 불필요한 추가연산을 하게 되는 경우가 있다. 아래 예시를 보자.
만일 nums가 [1, 0, 2, 4, 5, 0]라고 가정해보자. 그럼 연산순서는 아래와 같을 것이다.
[1, 0, 2, 4, 5, 0] -> [1, 2, 0, 4, 5, 0] -> [1, 2, 4, 0, 5, 0] -> [1, 2, 4, 5, 0, 0]
nums[2]에 0을 넣었다가 다시 4로 바꾸고 nums[3]도 0을 넣었다가 다시 5로 바꾼다.
두번째 방법은 배열을 탐색하면서 0이 아닌 숫자들을 앞에서부터 순서대로 집어넣고 그 뒤를 0으로 채우는 것이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class Solution { public void moveZeroes(int[] nums) { int index=0; //0이 아닌 숫자를 찾아서 앞에서부터 하나씩 채운다 for(int i=0 ; i<nums.length ; i++){ if(nums[i]!=0){ nums[index]=nums[i]; index++; } } //index뒤를 전부 0으로 바꾼다 while(index<nums.length){ nums[index]=0; index++; } } } | cs |
이렇게 하면 특정 위치의 값을 두번씩 바꾸는 일은 없겠지만 0의 갯수가 많을수록 0을 채워넣는 연산이 중복되는 경우가 생긴다(0을 또다시 0으로 채우는 경우). 이 방법도 동일하게 시간복잡도는 O(n), 공간복잡도는 O(1)이다.
문제출처 - https://leetcode.com/problems/move-zeroes/
'코딩문제(LeetCode) > Easy' 카테고리의 다른 글
| [코딩연습] Remove Outermost Parentheses 바깥 괄호 제거하기 (0) | 2019.05.05 |
|---|---|
| [코딩연습] Arranging Coins 동전 배열하기 (0) | 2019.04.26 |
| [코딩연습] Contains Duplicate 중복 포함 여부 (1) | 2019.04.24 |
| [코딩연습] Symmetric Tree 트리가 대칭인지 확인 (0) | 2019.04.21 |
| [코딩연습] Unique Morse Code Words 고유한 모스부호 가짓수 (0) | 2019.04.19 |
