문제
전제
고정 길이의 정수 배열 arr에 0이 발생 할 때마다 복제하고, 남은 요소들을 오른쪽으로 이동시킵니다.
Note 주어진 배열의 길이에 초과되는 요소들은 기록되지 않습니다.
위의 수정사항을 배열에 적용하고 아무것도 반환하지 않아도 됩니다.
예제1
입력 : arr = [1,0,2,3,0,4,5,0]
출력 : [1,0,0,2,3,0,0,4]
설명: 함수가 호출됐을때, 입력된 배열의 수정사항은 : [1,0,0,2,3,0,0,4] 입니다.
예제2
입력 : arr = [1,2,3]
출력 : [1,2,3]
설명 : 함수가 호출됐을때, 입력된 배열의 수정사항은 : [1,2,3] 입니다.
제약 조건
1 <= arr.length <= 104
0 <= arr[i] <= 9
Solution
class Solution {
public void duplicateZeros(int[] arr) {
int N = arr.length-1;
for(int i=0; i<N; i++){
if(arr[i]==0){
for(int j=N; j>i; j--){
arr[j]=arr[j-1];
}
i++;
}
}
}
}Runtime: 15 ms
Memory Usage: 45.8 MB
arr배열이 i번 반복하면서 i번째 배열의 값이 0일때 반복문을 통해 j의 값(arr의 길이)이
i값 보다 큰 동안 배열의 뒤에서부터 값들을 오른쪽으로 복사해주며 이동시켜줍니다.
ex) [1,0,2,3,0,4,5,0] -> [1,0,2,3,0,4,5,5] -> [1,0,2,3,0,4,4,5] -> . . . .-> [1,0,0,2,3,0,4,5]
해당 솔루션의 핵심은 전제조건인 배열의 길이를 초과되는 값은 기록하지 않기 때문에 배열의 값에 0을 확인했을때 마지막 값 부터 0이 확인된 배열의 index까지 왼쪽의 배열 값으로 복사해 나가는 겁니다.
하지만 상대적으로 느립니다.
최단시간
int length = arr.length - 1;
int possibleDup = 0;
for (int i = 0 ; i <= length - possibleDup; i++) {
if (arr[i] == 0) {
if (i == length - possibleDup) {
arr[length] = 0;
length--;
break;
}
possibleDup++;
}
}
int end = length - possibleDup;
while (end >= 0) {
if (arr[end] == 0) {
arr[length] = 0;
length--;
arr[length] = 0;
} else {
arr[length] = arr[end];
}
end--;
length--;
}첫번째 반복문에서 복제가능한 최대 길이를 구해낸 후 빠져나와 두번째 반복문에서
마지막 배열의 index가 0보다 작지 않을 때 값이 0인 경우를 비교하며 계속해서 값을 넣어줍니다.
재구성
class Solution {
public void duplicateZeros(int[] arr) {
int length = arr.length;
int possibleDup = 0;
int[] arr__ = new int[length+1];
for (int i = 0; i < length - possibleDup; i++) {
int j = i + possibleDup;
if (arr[i] == 0) {
arr__[j] = 0;
if(j+1 >= length) {
break;
}
arr__[j + 1] = 0;
possibleDup++;
}else{
arr__[j] = arr[i];
}
}
for (int i = 0 ; i < length ; i++) {
arr[i] = arr__[i];
}
}
}배열을 하나 더 생성하여 재구성했습니다.
arr__에 arr을 참조해 조건에 맞게 배열을 채워주고 마지막에 arr안에 arr__ 를 다시 입력 해줍니다.
배열을 하나 더 생성해야 하지만 최대길이를 구하며 값을 생성해내는 작업을 동시에 할 수 있습니다.
