배열을 돌리는 문제입니다.
처음에 단순히 or문을 2번 사용하면 되겠다고 생각했습니다.
즉, k번만큼 loop를 돌면서 nums를 다시 loop 탐색하여 값을 돌리는 것입니다.
하지만, 이 로직은 시간초과로 실패하였습니다.
K와 nums.length의 범위가 100,000이기 때문에 O(n2)의 시간복잡도로는 해결할 수 없습니다.
public void rotate(int[] nums, int k) {
for (int i = 0; i < k; i++) {
int temp = nums[nums.length-1];
for (int j = nums.length-1; j > 0; j--) {
nums[j] = nums[j - 1];
}
nums[0] = temp;
}
}
다른 시도
이번에는 temp배열을 만들어 k개만큼 데이터를 빼놓고
원본 배열을 이동시킨 후에 temp배열의 값을 원본에 넣으려고 시도해보았습니다.
하지만 예외처리 조건을 처리하지 못하여 실패하였습니다.
public void rotate(int[] nums, int k) {
int[] temp = new int[k];
int tempIdx = 0;
for (int i = nums.length - k; i < nums.length; i++) {
temp[tempIdx++] = nums[i];
}
// System.out.println(Arrays.toString(temp));
for (int i = nums.length-k-1; i >= 0; i--) {
nums[i+k] = nums[i];
}
for (int i = 0; i < temp.length; i++) {
nums[i] = temp[i];
}
// System.out.println(Arrays.toString(nums));
}
다른사람의 코드
%연산을 통해 배열안에서 2중 loop없이
순환하면서 탐색할 수 있었습니다.
public void rotate(int[] nums, int k) {
int[] temp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
temp[(i+k) % nums.length] = nums[i];
}
// System.out.println(Arrays.toString(temp));
for (int i = 0; i < nums.length; i++) {
nums[i] = temp[i];
}
System.out.println(Arrays.toString(nums));
}
느낀점
어떻게 해야 k번만큼 배열을 돌릴수 있을까? 에서
어떻게 O(n)의 시간복잡도로 줄일수 있을까라는 생각을 하였고
% 연산을 이용해 다른 복잡한 과정 없이 한번에 배열을 순환하면서 탐색할 수 있었습니다.
앞으로도 배열을 순환하는 로직이 필요하다면 %연산을 적극 활용해 봐야겠다고 생각했습니다.
참고
'LeetCode' 카테고리의 다른 글
[LeetCode] 122. Best Time to Buy and Sell Stock II (0) | 2023.08.25 |
---|---|
[LeetCode] 121. Best Time to Buy and Sell Stock (0) | 2023.08.25 |
[LeetCode] 169. Majority Element (1) | 2023.08.24 |
[LeetCode] 80. Remove Duplicates from Sorted Array II (0) | 2023.08.24 |
[LeetCode] 26 Remove Duplicates from Sorted Array (0) | 2023.08.24 |