반응형
1. 문제
- 고정 배열 arr이 주어질 때, 요소 중 0이 나오면 바로 다음 요소에 복제하고, 기존 요소들은 1칸 씩 뒤로 밀려진 배열을 구성하라.
- 새로운 배열을 사용하지 말고, 처음 제공되는 arr 배열을 수정하라. 배열 반환 X.
2. 해결
/**
Do not return anything, modify arr in-place instead.
*/
function duplicateZeros(arr: number[]): void {
let index = 0;
while(index <= arr.length-1) {
if(arr[index] !== 0) {
index++;
continue;
}
if(index >= arr.length-2) {
for(let i = index; i < arr.length; i++) {
arr[i] = 0;
}
} else {
for(let i = (arr.length - 2); i > index; i--) {
arr[i+1] = arr[i]
if(i === index+1) arr[i] = 0;
}
}
index+=2;
}
};- 코딩 테스트가 싫었던 이유가 다시 떠오른 문제.
- 일단, 내 풀이는 배열을 탐색하면서 0인 요소를 만나면 그 다음 인덱스 요소부터 한 칸씩 미루는 방식을 적용했고, 마지막에서 두 번째 요소는 예외 적으로 0인 경우는 끝까지 0으로 채우는 방식을 사용했다.
- 근데, 이 방식 통과는 되는데 20ms 걸리더라. 최악의 경우 O(N^2)가 걸리는 거 같다.
function duplicateZeros(arr: number[]): void {
let zeros = arr.filter(num => num === 0).length;
let n = arr.length;
// 뒤에서부터 역순으로 값 이동
for (let i = n - 1; i >= 0; i--) {
if (i + zeros < n) {
arr[i + zeros] = arr[i];
}
// '0'일 경우 한 번 더 복제
if (arr[i] === 0) {
zeros--;
if (i + zeros < n) {
arr[i + zeros] = 0;
}
}
}
}- 이 방식은 배열 내 존재하는 0의 개수 만큼 배열이 확장되는 구조에서 착안한 방법. (0이 3개 존재하면, length 8인 배열은 length 11이 된다고 생각.)
- 탐색 포인터 i, 삽입 위치 포인터 i + zeros를 이용해서 탐색해 나간다.
- 예를 들어, 10230450인 경우 0은 3개.
| i | zeros | i + zeros | element |
| 7 | 3 | 10 (삽입 위치가 초과, zeros--) | 0 - 그대로 |
| 6 | 2 | 8 (삽입 위치가 초과) | 5 - 그대로 |
| 5 | 2 | 7 (삽입 가능) | 4 (5번 인덱스 요소) -> 7번 인덱스 자리 |
| 4 | 2 | 6 (삽입 가능, zeros--) | 0 (4번 인덱스 요소) -> 6번 인덱스 자리 추가 0 -> 5번 인덱스 자리 |
| 3 | 1 | 4 (삽입 가능) | 3 (3번 인덱스 요소) -> 4번 인덱스 자리 |
| 2 | 1 | 3 (삽입 가능) | 2 (2번 인덱스 요소) -> 3번 인덱스 자리 |
| 1 | 1 | 2 (삽입 가능) | 0 (1번 인덱스 요소) -> 2번 인덱스 자리 추가 0 ->1번 인덱스 자리 |
| 0 | 0 | 0 (삽입 가능) | 1 (0번 인덱스 요소) -> 0번 인덱스 자리 |
- 위 단계를 거쳐서 삽입이 된다. 근데 이걸 문제 보고 어떻게 떠올려? =_=
- 이 문제를 통해 배운건 배열을 탐색할 때 효율적으로 하기 위해선 투 포인터!!!!를 고려해보자.