💬 문제
[문제 링크]
int 배열 nums를 k 만큼 오른쪽으로 회전
반환 값 없이 nums 내에서 회전
[1, 2, 3, 4, 5] k=2 는 [4, 5, 1, 2, 3]이 됨
✍️ 나의 풀이
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function(nums, k) {
const len = nums.length;
if (k % len === 0)
return ;
const copy = Array(...nums);
let idx = 0;
for (let i = 0; i < len; i++) {
idx = (i + k < len - 1) ? i + k : (i + k) % len;
nums[idx] = copy[i];
}
};k가 배열의 길이인 len과 같다면 결과도 원래의 배열과 같을 것이므로 바로 종료
nums와 똑같은 copy 배열을 보면서 nums는 비어있는 배열이라 생각하고 들어가야 할 자리에 대입
들어가야 할 자리는 현재 인덱스 i에 k를 더한 것이고, len과 같거나 커지면 len으로 나누어 앞에서부터 대입
📌 결과
Accepted
Runtime 95ms (Beats 66.74%)
Memory 51.6MB (Beats 70.82%)
📚 러닝 포인트
이번 문제에서 아마 가장 많이 헤매고 시도했던 것 같다. 처음에는 in-place와 다른 변수를 더 안쓰겠다는 것에 집착해서 swap으로 풀어보려다가 도저히 공통적인 행동이 나오지 않아서 포기하고, 중간중간 오른쪽으로 밀어야하는 것을 왼쪽으로 미는 것으로 착각하고 값이 이상하게 나와서 시간을 잡아먹는 등의 바보 같은 짓을 많이 했다. 결국에는 복사 배열을 만들고 들어가야하는 위치를 계산하는 방식으로 변경했지만 Array를 새로 만드는 것에 있어서 메모리 효율이 낮아지고, 전개 연산자를 사용하는 것에서 런타임 효율이 낮아지기 때문에 그 이전에 바로 반환할 수 있는 것들을 처리해주었지만 그래도 결과는 만족스럽지 못했다. 더 간단하고 효율적인 방법이 있을 것 같아 찾아보았다.
var rotate = function(nums, k) {
k %= nums.length
let reverse = function(i, j){
while(i < j){
let temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
i++
j--
}
}
reverse(0, nums.length-1) // reverse <--<------
reverse(0, k-1) // reverse first part ---><----
reverse(k, nums.length-1) // reverse second part --->----->
};다음과 같은 코드를 보게 되었는데, 이해하기 쉽도록 그림을 그리면 아래와 같다. 처음에 swap으로 컨셉을 잡았었지만 해결하지 못했었는데 이렇게 말끔한 코드를 보니 속이 시원하기도 하지만 역시 대단하다는 생각이 든다. k가 배열을 오른쪽으로 밀었을 때 얼마나 벗어나는 지에 대한 수 이므로 그만큼씩 끊어 다시 뒤집어 주면 회전한 형태가 되는 것이다. 어서 이런 생각에 미칠 수 있도록 사고력을 길러야지... 이번에는 가능할 뻔 했으나 끈기가 부족했다.
