[Java Script]LeetCode 189. Rotate Array

1. 문제 개요

문제 링크 : 189. Rotate Array

Rotate Array - LeetCode

• 주어진 배열을 함께 주어진 변수의 수만큼 회전하여라

2. 문제 풀이

단순하게 회전을 구현하는 문제여서 쉽게 접근하였지만 테스트 시 시간제한 초과라는 문제 때문에 많은 시행착오를 겪은 문제였습니다.

배열에서 값을 빼내 다시 배열에 넣어주는 방법을 보다 효율적으로 구상하기 위해 많은 시도가 있었습니다.

 

이를 구현하기 위해 주석으로 코드의 구조를 잡아보면 다음과 같습니다.

var rotate = function(nums, k) {
	// 반복하는 반복문 구현
    // 배열의 오른쪽 마지막 값을 제거하고 해당값을 저장
    // 배열의 왼쪽에 삽입
};

1차 시도

var rotate = function(nums, k) {
    for(let i = 0; i<k; i++){
        let value = nums.pop()
        nums.unshift(value)
    }
    console.log(nums)
};

가장 보면적으로 알려진 pop / unshift 이용하여 간단하게 구현하였으나 시간 초과로 통과하지 못했습니다.

 

2차 시도

가장 보면적으로 알려진 pop 연산이 원자의 길이수가 길어질수록 연산 효율이 떨어진다고 파악하여 pop 대신 직접 배열을 잘라서 구현하는 방법으로 구현하고 k의 값이 배열의 크기를 넘어설 때 필요 없는 연산을 할 필요 없게 % 연산을 통하여 효율화를 시도했습니다.

 

var rotate = function(nums, k) {
    k = k % nums.length
    for(i = 0; i<k; i++)nums.push(...nums.splice(0, nums.length -1))
};

 

하지만 이러한 2차 시도도 테스트 과정에서 배열의 크기가 엄청 커지자 시간제한이 발생하여 새로운 방법을 생각하였습니다.

3차 시도

3차 시도의 방식은 바로 반복문을 사용하지 않고 구현하는 방법입니다.

회전의 숫자가 배열의 크기보다 크다 보면 % 연산으로 그 횟수를 배열 아래로 줄이고

해당 개수만큼 끝에서 배열을 잘라 앞으로 붙이는 방법으로 구현했습니다.

 

var rotate = function(nums, k) {
    k = k % nums.length
    nums.unshift(...nums.splice(nums.length - k))
    console.log(nums)
};

 

 

이렇고 구현에 성공하였습니다.

 

3. 시간 복잡도 계산

splice의 시간복 작도가 O(n)입니다.

O(1) + O(n) = O(n)

 

4. 개선 사항

시간제한 초과로 인한  코드 수정 및 여러 개선사항이 발생하였습니다.

이를 통해 같은 문제를 해결하는 방법으로도 보다 효율적으로 해결할 수 있는 제3의 방법이 있음을 확인했습니다.

 

5. 깃허브

관련 사항은 깃허브에 모두 기재되어 있습니다.