https://leetcode.com/problems/rotate-array/description
정수 배열 nums를 k번 오른쪽으로 회전시키는 문제이다.
- 입력
- int[]int [] nums
- int k
- 출력
- void → nums 자체를 변경해야 한다.
문제 조건에서 nums와 k의 최대 값이 10^5로 상당히 크다
임시 배열을 만들어서 해결
int[] nums와 같은 크기의 임시 배열(int [] tmp)을 만들고 거기에 회전한 배열을 저장한다.
그 후 tmp의 값들로 nums를 덮어 씌우면 끝난다.
k만큼 오른쪽으로 회전한다는 것은 시작점이 이동되는 것과 마찬가지이다.
class Solution {
public void rotate(int[] nums, int k) {
int[] tmp = new int[nums.length];
int size = nums.length;
int start = size - k % size;
for (int i = 0; i < size; i++) {
tmp[i] = nums[(start + i) % size];
}
for (int i = 0; i < size; i++) {
nums[i] = tmp[i];
}
}
}
오른쪽으로 회전하고 있기 때문에 시작점 계산을 size - k % size로 처리한다.
이 시작점의 값이 새로운 tmp 배열의 첫 위치에 들어갈 값이 된다.
이제 배열의 크기만큼 순회하면서 채워 넣어주면 된다. 나머지 연산을 통해서 범위를 벗어나지 않도록 처리해 줬다.
하지만 이 풀이에는 문제가 있다. 별도의 추가 공간을 사용하고 있다는 점이다.
결국 nums 배열 자체를 수정해야 하는데 추가 공간을 사용하지 않고 수정할 수는 없을까?
배열의 반전
배열의 회전이란 것은 기준점을 두고 두 부분으로 나뉘고 그 두 부분의 위치가 바뀌는 것이다.
그런데 이 두 부분의 위치를 직접 바꾸면 시간복잡도가 증가하거나 추가 공간이 필요하게 된다.
이때 필요한 게 반전이다.
전체를 반전하게 되면 두 부분의 위치가 교환이 된다.
그러고 나서 각 부분을 다시 반전시키면 정상 순서로 위치만 바뀐 결과가 리턴된다.
즉 여기서 작성해야 할 코드는 특정 범위를 반전시키는 코드이다.
class Solution {
public void rotate(int[] nums, int k) {
int size = nums.length;
k = k % size;
reverse(nums, 0, size - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, size - 1);
}
private void reverse(int[] arr, int l, int r) {
while (l < r) {
// 교환
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
// 포인터 이동
l++;
r--;
}
}
}
반전은 해당 범위의 요소를 swap 해가며 반복하면 된다.
이를 통해서 추가 공간을 사용하지 않고 동시에 O(N)의 시간복잡도로 문제를 해결할 수 있었다.
'Algorithm > LeetCode' 카테고리의 다른 글
| LeetCode 55 - Jump Game (1) | 2024.09.29 |
|---|---|
| LeetCode 122 - Best Time to Buy and Sell Stock 2 (3) | 2024.09.28 |
| LeetCode 80 - Remove Duplicates from Sorted Array 2 (0) | 2024.09.28 |
| LeetCode 26 - Remove Duplicates from Sorted Array (0) | 2024.09.27 |
| LeetCode 27 - Remove Element (1) | 2024.09.27 |