[자료구조와 알고리즘] 189. Rotate Array

문제 설명

leetcode TopInterview150 - 189. Rotate Array

주어진 배열 nums를 k번 오른쪽으로 회전시키는 문제입니다. k는 음수가 나오지 않습니다.
이 문제는 세 가지 풀이법이 있다고 합니다.
follow up으로는 O(1)의 공간 복잡도로 제자리 알고리즘을 사용해보라고 제안하고 있습니다.

풀어보기

제자리 알고리즘으로 접근하면서 공간 복잡도를 어떻게 낮출 수 있을까 고민하다가
temp라는 임시 변수에 회전후 앞부분에 와야할 k개 배열을 저장하고
nums배열을 회전시킨뒤 채워주는 방식으로 풀어보았습니다.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    // k가 nums.length이상의 숫자일때 nums.length이하의 숫자로 줄여줍니다
    if (nums.length < k) k = k % nums.length;
  
	// 임시 변수에 회전후 앞부분에 배치할 k개의 배열 저장
 	let temp = nums.slice(nums.length-k);
  	// 배열의 뒷부분부터 채워주기 시작합니다
    for (let i=nums.length-1; i>=0; i--) {
        if (i < k) {
          	// 배열의 인덱스가 k보다 작다면 임시 배열에서 값을 가져옵니다
            nums[i] = temp[i]   
        } else {
            nums[i] = nums[i-k]
        }
    }
};

다른 풀이를 이용한 코드

전체 배열을 미리 뒤집어두고 회전할 부분을 나눠서 다시 뒤집는(?) 색다른 풀이를 발견했습니다.

var rotate = function(nums, k) {
   	k %= nums.length;
  
   	let reverse = function(i, j){
   		while(i < j){
          	// 임시 변수를 선언하는 것보다 유리한 구조 분해 할당!
        	[ nums[i], nums[j] ] = [ nums[j], nums[i] ];
        	i++;
        	j--;
    	}
   	}
	reverse(0, nums.length-1); 
	reverse(0, k-1);
   	reverse(k, nums.length-1);
    
};

예시를 넣어서 보면,
nums = [1,2,3,4,5,6,7]
k = 3

첫번째 reverse 후 : [7,6,5,4,3,2,1]
두번째 reverse 후 : [5,6,7, 4,3,2,1]
세번째 reverse 후 : [5,6,7, 1,2,3,4]

이렇게 풀 수도 있지만 제 풀이가 복잡도면에서 더 유리했습니다! 😆