Rotate Array 문제 해결 과정
medium, 정답률 39.2%
쉬운 문제인줄 알고 만만하게 봤는데 'In place' 조건이 붙으면서 고민을 해야했던 문제..
처음에 in place 상관 없이 생각한 방법은
nums 배열을 (nums.length-k)부터 (nums.length-1)까지 slice한 배열을 nums 맨 앞에 갖다 붙이는 것이었다.
그 이후 문제를 제대로 읽고 생각했던 로직을 수도코드로 나타내면
while i<k:
n=nums.length-1번째 요소 제거 후 대입
nums 맨 앞에 n 삽입
i++이렇게 되었는데.. 시간초과를 만났다.
var rotate = function(nums, k) {
let i=0
while(i<k){
let num=nums.splice(nums.length-1,1)
nums.unshift(num)
i++
}
};힌트를 보고 수정
리트코드 힌트와 다른 사람들이 푼 과정을 살펴보니 배열을 뒤집는 것을 이용했다.
예시 nums=[1,2,3,4,5,6,7] k=3를 살펴보면
처음에 전체 배열을 한 번 뒤집고..
[7,6,5,4,3,2,1]
rotate될 요소가 0번째 부터 k-1번째 까지 있으니 k를 기준으로 나눠서 생각해보면
[7,6,5] // [4,3,2,1]
0~k-1번째 요소들을 뒤집고, k번째부터 마지막 요소까지 뒤집는다.
[5,6,7,1,2,3,4]
하지만 추가 변수를 만들거나 배열 공간을 할당할 수는 없다.
또한 js에서 제공하는 reverse 함수는 전체 배열을 뒤집는것 밖에 할수가 없다.
따라서 인덱스별로 잘라 뒤집을 수 있는 reverse를 직접 구현해야 했다.
reverse 구현
배열이 있고 시작 인덱스, 끝 인덱스 변수를 만들어서 구현했다.
[1,2,3,4] 배열이 있고 시작 인덱스 0, 끝은 가장 마지막인 3에서 시작한다.
0번째와 3번째 요소를 swap [4,2,3,1]
시작 변수+1, 끝 변수-1
그다음 1번째와 2번째 요소를 swap한다 [4,3,2,1]
시작 변수+1, 끝 변수-1
시작 인덱스는 2, 끝 인덱스는 1이 되어 swap을 종료한다.
이런식으로 시작 인덱스 변수와 끝 인덱스 변수 값을 증가, 감소시켜 요소 값들을 서로 바꿀 수 있도록 구상했다.
function reverse(arr,start,end){
if(start<0 || end>arr.length || start>=end) return
let startIdx=start
let endIdx=end
while(startIdx<endIdx){
[arr[startIdx],arr[endIdx]]=[arr[endIdx],arr[startIdx]]
startIdx+=1
endIdx-=1
}
}swap은 js 구조분해할당을 이용해서 한 줄로 구현,
swap 반복 조건은 while로 작성했다.
이때 start,end가 배열 범위에 벗어나거나 start가 end보다 큰 경우 바로 종료한다.
최종
reverse 함수 구현을 바탕으로 한 메인함수이다.
var rotate = function(nums, k) {
if(nums.length<=1) return nums
if(k>=nums.length) k%=nums.length
reverse(nums,0,nums.length-1)
reverse(nums,0,k-1)
reverse(nums,k,nums.length-1)
};이때 처음에 k 조건을 보지 않고 if문 없이 reverse만 실행했을 때 틀린 답으로 처리됐다. k가 배열 크기보다 커질 수 있어 이 때는 mod 나머지 연산자로 k를 다시 세팅한다.
(문제에서는 규칙을 찾지 못해 틀렸을 때 디버깅하면서 알았다..)
추가로 nums 배열 요소가 하나일 때는 그대로 반환하도록 조건도 달았다.
결과는
Runtime: 91 ms
Memory Usage: 52.8 MB
특히 소요시간이 98.39% 앞서있다고 해서 기분이 좋았다..ㅋㅋㅋ
